Experience of event stream processing for top-k queries and dynamic graphs
Pages 330 - 335
Abstract
Solving 2016 ACM DEBS Grand Challenge problems entails both dynamic graph processing and top-k query processing. A straightforward implementation of solutions would not guarantee good performance or prompt responses. This paper shows our experience in implementing solutions of the problems, including rationales of top-k list management techniques we used in our implementation. We also shows the performance evaluation results among three top-k list management schemes and present the reason for our choice for the final result.
References
[1]
David Luckham. 2015. Complex Event Processing (CEP) Market -- Global forecast to 2019. http://www.complexevents.com/2015/01/31/complex-event-processing-cep-market-global-forecast-to-2019. Accessed: 2016-05-05.
[2]
Vincenzo Gulisano, Zbigniew Jerzak, Spyros Voulgaris, and Holger Ziekow. 2016. The DEBS 2016 grand challenge. In Proceedings of the 10th ACM International Conference on Distributed Event-Based Systems (DEBS '16). ACM, New York, NY, USA.
[3]
Orri Erling, Alex Averbuch, Josep Larriba-Pey, Hassan Chafi, Andrey Gubichev, Arnau Prat, Minh-Duc Pham, and Peter Boncz. 2015. The LDBC Social Network Benchmark: Interactive Workload. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data (SIGMOD '15). ACM, New York, NY, USA, 619--630.
[4]
Jonathan L. Gross, Jay Yellen, and Ping Zhang. 2013. Handbook of Graph Theory, Second Edition (2nd ed.). Chapman & Hall/CRC.
[5]
Patrick Prosser. 2012. Exact algorithms for maximum clique: A computational study. Algorithms 5, 4 (2012).
[6]
William Pugh. 1990. Skip lists: a probabilistic alternative to balanced trees. Commun. ACM 33, 6 (June 1990), 668--676.
[7]
Thompson, Martin; Farley, Dave; Barker, Michael; Gee, Patricia; Stewart, Andrew (2011). Disruptor: High performance alternative to bounded queues for exchanging data between concurrent threads. Technical report. LMAX
[8]
Sample set of input data streams: 2016. https://www.dropbox.com/s/vo83ohrgcgfqq27/data.tar.bz2. Accessed: 2016-05-05.
[9]
Ihab F. Ilyas, George Beskales, and Mohamed A. Soliman. 2008. A survey of top-k query processing techniques in relational database systems. ACM Comput. Surv. 40, 4, Article 11 (October 2008), 58 pages.
[10]
Ronald Fagin, Amnon Lotem, and Moni Naor. 2001. Optimal aggregation algorithms for middleware. In Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems (PODS '01). ACM, New York, NY, USA, 102--113.
[11]
Zhitao Shen, Muhammad Aamir Cheema, Xuemin Lin, Wenjie Zhang, and Haixun Wang. 2012. Efficiently Monitoring Top-k Pairs over Sliding Windows. In Proceedings of the 2012 IEEE 28th International Conference on Data Engineering (ICDE '12). IEEE Computer Society, Washington, DC, USA, 798--809.
[12]
Kyriakos Mouratidis, Spiridon Bakiras, and Dimitris Papadias. 2006. Continuous monitoring of top-k queries over sliding windows. In Proceedings of the 2006 ACM SIGMOD international conference on Management of data (SIGMOD '06). ACM, New York, NY, USA, 635--646.
Index Terms
- Experience of event stream processing for top-k queries and dynamic graphs
Recommendations
Time- and Space-Efficient Sliding Window Top-k Query Processing
A sliding window top-k (top-k/w) query monitors incoming data stream objects within a sliding window of size w to identify the k highest-ranked objects with respect to a given scoring function over time. Processing of such queries is challenging because,...
Processing a large number of continuous preference top-k queries
SIGMOD '12: Proceedings of the 2012 ACM SIGMOD International Conference on Management of DataGiven a set of objects, each with multiple numeric attributes, a (preference) top-k query retrieves the k objects with the highest scores according to a user preference, defined as a linear combination of attribute values. We consider the problem of ...
Scalable and efficient processing of top-k multiple-type integrated queries
AbstractIn this paper, we define a new class of queries, the top-k multiple-type integrated query (simply, top-k MULTI query). It deals with multiple data types and finds the information in the order of relevance between the query and the object. Various ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2016
456 pages
ISBN:9781450340212
DOI:10.1145/2933267
- General Chairs:
- Avigdor Gal,
- Matthias Weidlich,
- Program Chairs:
- Vana Kalogeraki,
- Nalini Venkasubramanian
Copyright © 2016 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 13 June 2016
Check for updates
Author Tags
Qualifiers
- Research-article
Funding Sources
- Ministry of Education
Conference
DEBS '16: The 10th ACM International Conference on Distributed and Event-based Systems
June 20 - 24, 2016
California, Irvine
Acceptance Rates
Overall Acceptance Rate 145 of 583 submissions, 25%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 153Total Downloads
- Downloads (Last 12 months)1
- Downloads (Last 6 weeks)0
Reflects downloads up to 03 Oct 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in