Subhodeep Ghosh, Zhihui Du, Bonifati, Angela et al. · ArXiv.org · 2026
We study the problem of enforcing continuous group fairness over windows in data streams. We propose a novel fairness model that ensures group fairness at a finer granularity level (referred to as block) within each sliding window. This formulation is particularly useful when the window size is large, making it desirable to enforce fairness at a finer granularity. Within this framework, we address two key challenges: efficiently monitoring whether each sliding window satisfies block-level group fairness, and reordering the current window as effectively as possible when fairness is violated. To enable real-time monitoring, we design sketch-based data structures that maintain attribute distributions with minimal overhead. We also develop optimal, efficient algorithms for the reordering task, supported by rigorous theoretical guarantees. Our evaluation on four real-world streaming scenarios demonstrates the practical effectiveness of our approach. We achieve millisecond-level processing and a throughput of approximately 30,000 queries per second on average, depending on system parameters. The stream reordering algorithm improves block-level group fairness by up to 95% in certain cases, and by 50-60% on average across datasets. A qualitative study further highlights the advantages of block-level fairness compared to window-level fairness.
Cited by 0Open access
Subhodeep Ghosh, Zhihui Du, Bonifati, Angela et al. · arXiv (Cornell University) · 2026
We study the problem of enforcing continuous group fairness over windows in data streams. We propose a novel fairness model that ensures group fairness at a finer granularity level (referred to as block) within each sliding window. This formulation is particularly useful when the window size is large, making it desirable to enforce fairness at a finer granularity. Within this framework, we address two key challenges: efficiently monitoring whether each sliding window satisfies block-level group fairness, and reordering the current window as effectively as possible when fairness is violated. To enable real-time monitoring, we design sketch-based data structures that maintain attribute distributions with minimal overhead. We also develop optimal, efficient algorithms for the reordering task, supported by rigorous theoretical guarantees. Our evaluation on four real-world streaming scenarios demonstrates the practical effectiveness of our approach. We achieve millisecond-level processing and a throughput of approximately 30,000 queries per second on average, depending on system parameters. The stream reordering algorithm improves block-level group fairness by up to 95% in certain cases, and by 50-60% on average across datasets. A qualitative study further highlights the advantages of block-level fairness compared to window-level fairness.
Cited by 0Open access
Shivnath Babu, et al. · 2008
In many recent applications, data may take the form of continuous data streams, rather than finite stored data sets. Several aspects of data management need to be reconsidered in the presence of data streams, offering a new research direction for the database community. In this paper we focus primarily on the problem of query processing, specifically on how to define and evaluate continuous queries over data streams. We address semantic issues as well as efficiency concerns. Our main contributions are threefold. First, we specify a general and flexible architecture for query processing in the presence of data streams. Second, we use our basic architecture as a tool to clarify alternative semantics and processing techniques for continuous queries. The architecture also captures most previous work on continuous queries and data streams, as well as related concepts such as triggers and materialized views. Finally, we map out research topics in the area of query processing over data streams, showing where previous work is relevant and describing problems yet to be addressed.
Cited by 0
Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 2007
Cited by 0
Jia Cui, Weiping Wang, Dan Meng et al. · 2014
Similarity join plays an important role in many applications, such as data cleaning and integration, to address the poor data quality problem. Most of the existing studies focused on performing similarity join on static datasets but few studies realized running it on dynamic data streams. With the development of network technology, the data accessing paradigm has transferred from disk-oriented mode to online data streams, which makes performing similarity join in continuous query on data streams become a novel query processing paradigm. Different from static dataset, data stream is unbounded, continuous and unpredictable. The significant differences pose serious challenges, such as real-time query performance. To this end, we study the problem of continuous similarity join on data streams in this paper, which is based on edit distance metric and filter-and-verify framework with sliding-window semantics. Two subcases of this problem are studied, including self similarity join on a single data stream and similarity join on two streams. We introduced the basic window based sliding window model to facilitate the update of sliding window and its index. More details of our method, including signature extraction schemes, filtering and verification algorithms, re-evaluation strategies are discussed respectively. Finally, extensive experimental results show that our method works efficiently on real data streams.
Cited by 1
Antal Buza · 2005
Cited by 0
Sharma Chakravarthy, Qingchun Jiang · The Kluwer international series on advances in database systems · 2009
Cited by 0
Papadias, Dimitris, Papadopoulos, Stavros · Rare & Special e-Zone (The Hong Kong University of Science and Technology) · 2007
We study processing and authentication of long-running queries on outsourced data streams. In this scenario, a data owner (DO) constantly transmits its data to a service provider (SP), together with additional authentication information. Clients register continuous range queries to the SP. Whenever the data change, the SP must update the results of all affected queries and inform the clients accordingly. The clients can verify the correctness of the results using the authentication information provided by the DO. Compared to conventional databases, stream environments pose new challenges such as the need for fast structure updating, support for continuous query processing and authentication, and provision for temporal completeness. Specifically, in addition to the correctness of individual results, the client must be able to verify that there are no missing results in between updates. We face these challenges through several contributions. Since there is no previous work, we first present a technique, called REF, that achieves correctness and temporal completeness but incurs false transmissions, i.e., the SP has to inform clients whenever there is a data update, even if their results are not affected. Then, we propose CADS, which minimizes the processing and transmission overhead through an elaborate indexing scheme and a virtual caching mechanism. Finally, we extend CADS to the case where multiple owners outsource their data to the same SP. The SP integrates all data in a single authentication process, independently of the number of DOs.
Cited by 0
Hyeon Cheol Kim, CheolGi Kim, Myoung Kim · 2006
A disorder control is the key factor regarding accuracy and latency of query results when processing sliding window aggregates over continuous data streams. Many stream systems maintain buffers or leverage punctuations for the control. However, current systems suffer from the lack of adaptivity in the measure for estimating buffer sizes or punctuations, which may lead to inaccurate or delayed query results. To address this problem, we propose a probabilistic approach to using an adaptive measure derived from the distributions of tuple generation intervals and network latencies. In our approach, the measure estimates buffer sizes or punctuations according to a drop ratio, which denotes a percentage of tuple drops permissible in run-time processing. The drop ratio can be defined declaratively in a query specification and it provides a way for users to control the tuple drops as their intention. The experimental results show that our adaptive measure estimates more appropriate buffer sizes than ad hoc measures, which means that the proposed measure provides a lower latency, while retaining accuracy by satisfying the given drop ratio.
Cited by 0
Peter Tucker, David Maier, Tim Sheard et al. · IEEE Transactions on Knowledge and Data Engineering · 2003
As most current query processing architectures are already pipelined, it seems logical to apply them to data streams. However, two classes of query operators are impractical for processing long or infinite data streams. Unbounded stateful operators maintain state with no upper bound in size and, so, run out of memory. Blocking operators read an entire input before emitting a single output and, so, might never produce a result. We believe that a priori knowledge of a data stream can permit the use of such operators in some cases. We discuss a kind of stream semantics called punctuated streams. Punctuations in a stream mark the end of substreams allowing us to view an infinite stream as a mixture of finite streams. We introduce three kinds of invariants to specify the proper behavior of operators in the presence of punctuation. Pass invariants define when results can be passed on. Keep invariants define what must be kept in local state to continue successful operation. Propagation invariants define when punctuation can be passed on. We report on our initial implementation and show a strategy for proving implementations of these invariants are faithful to their relational counterparts.
Cited by 311
Bhawna Suri · 2015
Abstract — Data stream is a continuous, real time, multidimensional, ordered sequence of data elements produced by the data source. The efforts have been made to do the analytic processing on data streams. In order to do so, a portion of the stream is captured in a window and is mapped to the multidimensional structure onto which the existing OLAP operations are applied. We have also worked on the same approach but here the multidimensional structure- Cube is analyzed using two new OLAP operations. These OLAP operations are Virtual- Rollup and Restrict. This paper aim towards a new angle of handling continuous analysis of data stream data using the new set of OLAP operators. Keywords-data streams, OLAP.
Cited by 0
Maria Kontaki, Apostolos N. Papadopoulos, Yannis Manolopoulos · Lecture notes in computer science · 2008
Cited by 22
Ricardo Jesus, Mário Antunes, Diogo Gomes et al. · Portuguese National Funding Agency for Science, Research and Technology (RCAAP Project by FCT) · 2018
The untapped source of information, extracted from the increasing number of sensors, can be explored to improve and optimize several systems. Yet, hand in hand with this growth goes the increasing difficulty to manage and organize all this new information. The lack of a standard context representation scheme is one of the main struggles in this research area. Conventional methods for extracting knowledge from data rely on a standard representation or a priori relation, which may not be feasible for IoT and M2M scenarios. With this in mind we propose a stream characterization model in order to provide the foundations for a novel stream similarity metric. Complementing previous work on context organization, we aim to provide an automatic stream organizational model without enforcing specific representations. In this paper we extend our work on stream characterization and devise a novel similarity method.
Cited by 1Open access
Stavros Papadopoulos, Yin Yang, Dimitris Papadias · 2007
We study processing and authentication of long-running queries on outsourced data streams. In this scenario, a data owner (DO) constantly transmits its data to a service provider (SP), together with additional authentication information. Clients register continuous range queries to the SP. Whenever the data change, the SP must update the results of all affected queries and inform the clients accordingly. The clients can verify the correctness of the results using the authentication information provided by the DO. Compared to conventional databases, stream environments pose new challenges such as the need for fast structure updating, support for continuous query processing and authentication, and provision for temporal completeness. Specifically, in addition to the correctness of individual results, the client must be able to verify that there are no missing results in between updates. We face these challenges through several contributions. Since there is no previous work, we first present a technique, called REF, that achieves correctness and temporal completeness but incurs false transmissions, i.e., the SP has to inform clients whenever there is a data update, even if their results are not affected. Then, we propose CADS, which minimizes the processing and transmission overhead through an elaborate indexing scheme and a virtual caching mechanism. Finally, we extend CADS to the case where multiple owners outsource their data to the same SP. The SP integrates all data in a single authentication process, independently of the number of DOs. 1.
Cited by 0
Lin Qiao, Divy Agrawal, Amr El Abbadi · 2002
Many applications, such as network monitoring and telecommunication applications, depend critically on the efficient processing of data streams. Maintaining approximate aggregates and summaries over data streams is crucial to handle the OLAP query workload that arises in such applications. Furthermore, since the entire data is not available at all times the maintenance task must be done incrementally. We show that R(elaxed)Hist(ogram) is an appropriate summarization under data stream scenario. In order to reduce query estimation errors, we propose adaptive approaches which not only capture the data distribution, but also integrate independent query patterns. We introduce a workload decay model to eciently capture global workload information and ensure that query patterns from the recent past are weighted more than queries that are further in the past. An advanced adaptive algorithm based on suitable threshold function is proposed for our workload decay model. The algorithm adapts the histogram to user query workloads for more accurate estimate of the range queries over data streams. We verify experimentally that our approach successfully adapts to changes in the workload as well as continuing changing data streams.
Cited by 0
Hyeon-Gyu KIM, Woo-Lam Kang, Yoon-Joon Lee et al. · IEICE Transactions on Information and Systems · 2009
In this paper, we propose a predicate indexing method which handles equality and inequality tests separately. Our method uses a hash table for the equality test and a balanced binary search tree for the inequality test. Such a separate structure reduces a height of the search tree and the number of comparisons per tree node, as well as the cost for tree rebalancing. We compared our method with the IBS-tree which is one of the popular indexing methods suitable for data stream processing. Our experimental results show that the proposed method provides better insertion and search performances than the IBS-tree.
Cited by 0Open access
Hong Kyu Park, Won Suk Lee · 2008
Query processing for data streams should be continuous and rapid, which requires strict time constraint. In most previous researches, in order to guarantee this constraint, the evaluation order of join predicates in a continuous query is optimized by a greedy. However, the greedy strategy traces only the first promising plan, so that it often finds a sub-optimal plan. This paper proposes an improved scheme called an Adaptively Sharing-based Extended Greedy Algorithm(A-SEGO). Given continuous queries with multiple join operations, they simultaneously trace a set of promising plans to reduce the possibility of producing a sub-optimal plan. Also it can control the time to optimize continuous queries depending the current processing load by controlling the number of traced plans. Experiment results illustrate the performance of the A-SEGO in various stream environments.
Cited by 2
Herrtwich, R.G. · Publikationsdatenbank der Fraunhofer-Gesellschaft (Fraunhofer-Gesellschaft) · 1990
Cited by 1
Ελευθέριος Ζερβάκης · 2019
Στη σύγχρονη ψηφιακή εποχή, η δημιουργία και η διάθεση νέας πληροφορίας γίνεται με ταχείς ρυθμούς. Η επιλεκτική διάχυση πληροφορίας (information dissemination, publish/subscribe) έχει αναπτυχθεί ως το μέσο για την διευκόλυνση της αναζήτησης και έγκαιρης διάδοσης πληροφορίας στους χρήστες, καθώς και της ανακάλυψης νέου και ενδιαφέροντος περιεχομένου.Τα τελευταία χρόνια, η επιστημονική έρευνα στον τομέα της διάχυσης πληροφορίας έχει επικεντρωθεί στην αναπαράσταση των ενδιαφερόντων των χρηστών που εκφράζονται μέσω της δημιουργίας προφίλ (π.χ., εγγραφές σε υπηρεσίες παροχής ειδήσεων, δημιουργία προφίλ σε κοινωνικά δίκτυα κ.λ.π.) και στην αποτελεσματική και γρήγορη διανομή της πληροφορίας στους χρήστες, όταν αυτή γίνει διαθέσιμη. Ο τεράστιος όγκος δεδομένων όμως που γίνεται διαθέσιμος καθημερινά στον Παγκόσμιο Ιστό απαιτεί αποτελεσματικούς αλγόριθμους τόσο για την αναπαράσταση και ευρετηρίαση των προφίλ (profile creation, profile indexing), όσο και για το φιλτράρισμα της νέας διαθέσιμης πληροφορίας (publication filtering, information dissemination, mutli-query processing). Η παρούσα διατριβή στοχεύει στην επίλυση των παραπάνω προβλημάτων χρησιμοποιώντας σύγχρονες μορφές αναπαράστασης δεδομένων (RDF data, graph data), και προτείνοντας δομές δεδομένων και αλγόριθμους για την διαχείριση του μεγάλου όγκου πληροφορίας. Η παρούσα έρευνα μελέτησε λύσεις ευρετηρίασης και φιλτραρίσματος πληροφορίας κειμένου βασισμένες σε δεντρικές δομές (trie-based profile indexing), σχεδίασε και ανέπτυξε αλγορίθμους για την ευρετηρίαση δεδομένων μεγάλου όγκου που έχουν ληφθεί από μια πληθώρα συλλογών κειμένων. Οι προτεινόμενοι αλγόριθμοι αξιολογήθηκαν πειραματικά και τα αποτελέσματα που προκύπτουν από την αξιολόγηση υποδεικνύουν βελτίωση έως και δυο τάξεις μεγέθους σε σύγκριση με υπάρχουσες λύσεις της βιβλιογραφίας. Τα αποτελέσματα της έρευνας μας επισημαίνουν ως καίριο παράγοντα βελτιστοποίησης της αποτελεσματικής απόδοσης του φιλτραρίσματος τις δεντρικές δομές. Πιο συγκεκριμένα, τα αποτελέσματα υποδεικνύουν ότι η μορφολογία και οργάνωση των δεντρικών δομών είναι ο καθοριστικός παράγοντας βελτιστοποίησης, σε αντίθεση με την μέχρι έως τώρα πεποίθηση ότι το μέγεθος των δεντρικών δομών (forest compactness) αποτελεί τον κύριο παράγοντα απόδοσης. Σε συνέχεια της παρούσας έρευνας, σχεδιάσθηκαν και αναπτύχθηκαν αλγορίθμοι για την ευρετηρίαση και το φιλτράρισμα δεδομένων που αναπαριστώνται στο μοντέλο δεδομένων RDF. Επιπρόσθετα, προτείναμε μια καινοτόμα επέκταση της γλώσσας ερωτήσεων SPARQL, η οποία στοχεύει στην αύξηση της εκφραστικότητας των ερωτήσεων των χρηστών μέσω της παροχής τελεστών κειμένου (full-text operators). Οι αλγόριθμοι που σχεδιάστηκαν και αναπτύχθηκαν αξιολογήθηκαν πειραματικά, και τα αποτελέσματα που προκύπτουν από την αξιολόγηση υποδεικνύουν βελτίωση έως και δύο τάξεις μεγέθους σε σύγκριση με υπάρχουσες καινοτόμες λύσεις της βιβλιογραφίας.Επιπλέον, η έρευνα μας στόχευσε στη σχεδίαση και ανάπτυξη αλγορίθμων για την ευρετηρίαση και την αξιολόγηση ερωτήσεων σε ροές δεδομένων για γράφους. Η παρούσα έρευνα είναι η πρώτη στη βιβλιογραφία η οποία εισάγει την συνεχή αξιολόγηση πολλαπλών ερωτήσεων (mutli-query processing) πάνω από ροές δεδομένων για γράφους. Πιο συγκεκριμένα, σχεδιάσαμε και αναπτύξαμε τέσσερις νέους αλγορίθμους με σκοπό την μελέτη και αξιολόγηση της απόδοσης διαφορετικών προσεγγίσεων ευρετηρίασης προφίλ. Η αξιολόγηση στόχευσε στην εκτίμηση της απόδοσης των αλγορίθμων σε ένα ευρύ πεδίο εφαρμογών, όπως τα κοινωνικά δίκτυα (Social Networks), τα δίκτυα κίνησης οχημάτων σε αστικά κέντρα (Road Networks), και οι γράφοι αλληλεπιδράσεων πρωτεϊνών (Protein-to-Protein Interaction Graphs), και στην αξιολόγηση και στην σύγκριση των σχεδιασθέντων αλγορίθμων με υπάρχουσες εμπορικές λύσεις. Τα αποτελέσματα της πειραματικής αξιολόγησης τονίζουν την ανάγκη για ανάπτυξη εξιδεικευμένων λύσεων σχεδιασμένων για συνεχή αξιολόγηση ερωτήσεων σε ροές δεδομένων γράφων, καθώς παρατηρήθηκε βελτίωση του χρόνου φιλτραρίσματος κατά δυο τάξεις μεγέθους ανάμεσα στους προτεινόμενους αλγόριθμους και στις πιο απλοϊκές προσεγγίσεις.Τέλος, η έρευνα μας επικεντρώθηκε στην σχεδίαση και ανάπτυξη ενός καινοτόμου, πλήρως λειτουργικού, συστήματος φιλτραρίσματος πληροφορίας κειμένου, με την ονομασία Ping. Η ανάπτυξη του συστήματος Ping στόχευσε στη μελέτη υπαρχόντων τεχνολογικών λύσεων υπό το φως της διάχυσης πληροφορίας, και στη δημιουργία ενός πλήρως λειτουργικού συστήματος παροχής υπηρεσιών φιλτραρίσματος για τους χρήστες. Η δημιουργία ενός τέτοιου συστήματος αναδεικνύει την εφαρμοσιμότητα προηγμένων τεχνολογικών λύσεων στον τομέα της διάχυσης πληροφορίας.
Cited by 2
Reynold Cheng, Ben Kao, Alan Kwan et al. · IEEE Transactions on Knowledge and Data Engineering · 2009
The idea of allowing query users to relax their correctness requirements in order to improve performance of a data stream management system (e.g., location-based services and sensor networks) has been recently studied. By exploiting the maximum error (or tolerance) allowed in query answers, algorithms for reducing the use of system resources have been developed. In most of these works, however, query tolerance is expressed as a numerical value, which may be difficult to specify. We observe that in many situations, users may not be concerned with the actual value of an answer, but rather which object satisfies a query (e.g., "who is my nearest neighbor?¿). In particular, an entity-based query returns only the names of objects that satisfy the query. For these queries, it is possible to specify a tolerance that is "nonvalue-based.¿ In this paper, we study fraction-based tolerance, a type of nonvalue-based tolerance, where a user specifies the maximum fractions of a query answer that can be false positives and false negatives. We develop fraction-based tolerance for two major classes of entity-based queries: 1) nonrank-based query (e.g., range queries) and 2) rank-based query (e.g., k-nearest-neighbor queries). These definitions provide users with an alternative to specify the maximum tolerance allowed in their answers. We further investigate how these definitions can be exploited in a distributed stream environment. We design adaptive filter algorithms that allow updates be dropped conditionally at the data stream sources without affecting the overall query correctness. Extensive experimental results show that our protocols reduce the use of network and energy resources significantly.
Cited by 13