Cited By
View all- Wang RLu STao Y(2023)An Index for Set Intersection With Post-FilteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3329145(1-14)Online publication date: 2023
Answering Spatial Multiple-Set Intersection Queries Using 2-3 Cuckoo Hash-Filters
Article No.: 65, Pages 1 - 4
Abstract
We show how to answer spatial multiple-set intersection queries in O(n(log w)/w + kt) expected time, where n is the total size of the t ≤ wc sets involved in the query, w is the number of bits in a memory word, k is the output size, and c ≥ 1 is any fixed constant.
References
[1]
Susanne Albers and Torben Hagerup. 1997. Improved Parallel Integer Sorting without Concurrent Writing. Inf. & Comput. 136, 1 (1997), 25--51.
[2]
Philip Bille, Anna Pagh, and Rasmus Pagh. 2007. Fast evaluation of union-intersection expressions. In Int. Symp. Algorithms and Computation (LNCS), Vol. 4835. Springer, 739--750.
[3]
Bolin Ding and Arnd Christian König. 2011. Fast Set Intersection in Memory. Proc. VLDB Endow. 4, 4 (Jan. 2011), 255--266.
[4]
David Eppstein. 2016. Cuckoo Filter: Simplification and Analysis. In 15th Scand. Workshop on Algorithm Theory (LIPIcs), Vol. 53. 8:1--8:12.
[5]
David Eppstein and Michael T. Goodrich. 2017. Brief Announcement: Using Multi-Level Parallelism and 2-3 Cuckoo Filters for Set Intersection Queries and Sparse Boolean Matrix Multiplication. In 29th ACM Symp. on Parallelism in Algorithms and Architectures (SPAA).
[6]
David Eppstein, Michael T. Goodrich, Michael Mitzenmacher, and Manuel R. Torres. 2017. 2--3 Cuckoo Filters for Faster Triangle Listing and Set Intersection. In 36th ACM Symp. on Principles of Database Systems. 247--260.
[7]
Michael T. Goodrich. 2017. Answering Spatial Multiple-Set Intersection Queries Using 2-3 Cuckoo Hash-Filters. ArXiv ePrint 1708.09059 (2017). arxiv.org/abs/1708.09059
[8]
Torben Hagerup. 1998. Sorting and searching on the word RAM. In 15th Symp. on Theor. Aspects of Comp. Sci. 366--398.
[9]
Torben Hagerup. 2000. Improved Shortest Paths on the Word RAM. In 27th Int. Colloqium on Automata, Languages and Programming. Springer, 61--72.
[10]
Tsvi Kopelowitz, Seth Pettie, and Ely Porat. 2015. Dynamic Set Intersection. In 14th Symp. on Algorithms and Data Structures (SODA). 470--481.
[11]
Peter Bro Miltersen. 1996. Lower bounds for static dictionaries on RAMs with bit operations but no multiplication. In 23rd Int. Colloq. on Automata, Languages and Programming (ICALP) (LNCS), Vol. 1099. Springer, 442--453.
[12]
Dan E. Willard. 2000. Examining Computational Geometry, Van Emde Boas Trees, and Hashing from the Perspective of the Fusion Tree. SIAM J. Comput. 29, 3 (2000), 1030--1049.
[13]
Xiao Yang, Manish Vachharajani, and Ruby B. Lee. 1999. Fast subword permutation instructions based on butterfly network. In Proc. SPIE, Vol. 3970. 80--86.
Index Terms
- Answering Spatial Multiple-Set Intersection Queries Using 2-3 Cuckoo Hash-Filters
Recommendations
2-3 Cuckoo Filters for Faster Triangle Listing and Set Intersection
PODS '17: Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database SystemsWe introduce new dynamic set intersection data structures, which we call 2-3 cuckoo filters and hash tables. These structures differ from the standard cuckoo hash tables and cuckoo filters in that they choose two out of three locations to store each ...
Closest-pair queries in fat rectangles
AbstractIn the range closest pair problem, we want to construct a data structure storing a set S of n points in the plane, such that for any axes-parallel query rectangle R, the closest pair in the set R ∩ S can be reported. The currently best ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
November 2017
677 pages
ISBN:9781450354905
DOI:10.1145/3139958
Copyright © 2017 Owner/Author.
Permission to make digital or hard copies of part or all 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 third-party components of this work must be honored. For all other uses, contact the Owner/Author.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 07 November 2017
Check for updates
Author Tags
Qualifiers
- Poster
- Research
- Refereed limited
Funding Sources
Conference
SIGSPATIAL'17
Sponsor:
SIGSPATIAL'17: 25th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems
November 7 - 10, 2017
CA, Redondo Beach, USA
Acceptance Rates
SIGSPATIAL '17 Paper Acceptance Rate 39 of 193 submissions, 20%;
Overall Acceptance Rate 257 of 1,238 submissions, 21%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 244Total Downloads
- Downloads (Last 12 months)43
- Downloads (Last 6 weeks)6
Reflects downloads up to 23 Nov 2024
Other Metrics
Citations
Cited By
View all- Wang RLu STao Y(2023)An Index for Set Intersection With Post-FilteringIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2023.3329145(1-14)Online publication date: 2023
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in