Efficient Top-k Spatial Dataset Search Processing
Source abstract
Abstract
In this paper, we introduce two novel top-k spatial dataset search schemes, KSDS and KSDS+. The core innovation of these schemes lies in partitioning the spatial datasets into grids and assessing similarity based on the distribution of points within these grids. This approach provides a robust foundation for spatial dataset search. To optimize search performance, we have developed an optimized scheme that incorporates two key strategies: a GMBR-based optimization strategy and a pooling-based optimization strategy. These strategies are designed to filter datasets to significantly improve search efficiency. Our experimental results demonstrate that KSDS and KSDS+ can perform top-k spatial dataset searches with both high effectiveness and efficiency, outpacing existing methods in terms of search speed. In the future, our research will explore other similarity-calculation models to further accelerate processing times. Additionally, we aim to integrate privacy-preserving techniques to ensure secure dataset searches. These advancements are intended to enhance the practicality and efficiency of spatial dataset searches in real-world applications.
Source: crossref · Quality: baseline
Research context
OpenAlex topics: Data Management and Algorithms · Data Mining Algorithms and Applications
SciVX discovery tags are terminology-based. OpenAlex topics are source-provided classifications.
Affiliations
School of Computer Science, Nanjing University of Posts and Telecommunications, Nanjing 210023, China
Funding
National Natural Science Foundation of China · Jiangsu Province Postgraduate Scientific Research Innovation Program
References (25)
Show source-provided references
1. Yew, J.X., Liao, N., Mo, D., and Luo, S. (2023, January 3–7). Example Searcher: A spatial query system via example. Proceedings of the IEEE 39th International Conference on Data Engineering (ICDE), Anaheim, CA, USA.10.1109/ICDE55515.2023.00286 ↗
2. Vasconcelos, P.A.F., Alencar, W.d.S., Ribeiro, V.H.S., Rodrigues, N.F., and Andrade, F.G. (2017, January 28–31). Enabling spatial queries in open government data portals. Proceedings of the 6th International Conference on 579 Electronic Government and the Information Systems Perspective (EGOVIS), Lyon, France.
3. Bogatu, A., Fernandes, A.A.A., Paton, N.W., and Konstantinou, N. (2020, January 20–24). Dataset discovery in data lakes. Proceedings of the IEEE 36th International Conference on Data Engineering (ICDE), Dallas, TX, USA.10.1109/ICDE48307.2020.00067 ↗
4. Chen, Z., Jia, H., Heflin, J., and Davison, B.D. (2020, January 14–17). Leveraging schema labels to enhance dataset search. Proceedings of the Advances in Information Retrieval: 42nd European Conference on IR Research (ECIR), Lisbon, Portugal.10.1007/978-3-030-45439-5_18 ↗
5. Dong, Y., Takeoka, K., Xiao, C., and Oyamada, M. (2021, January 19–22). Efficient joinable table discovery in data lakes: A high-dimensional similarity-based approach. Proceedings of the IEEE 37th International Conference on Data Engineering (ICDE), Chania, Greece.10.1109/ICDE51399.2021.00046 ↗
6. Nargesian, F., Pu, K.Q., Zhu, E., Bashardoost, B.G., and Miller, R.J. (2020, January 14–19). Organizing data lakes for navigation. Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data (SIGMOD), Portland, OR, USA.10.1145/3318464.3380605 ↗
7. Auctus: A dataset search engine for data discovery and augmentation10.14778/3476311.3476346 ↗
8. RONIN: Data lake exploration10.14778/3476311.3476364 ↗
9. Degbelo, A., and Bahrishum, B. (2019, January 5). Spatial search strategies for open government data: A systematic comparison. Proceedings of the 13th ACM SIGSPATIAL Workshop on Geographic Information Retrieval (GIR), Chicago, IL, USA.10.1145/3371140.3371142 ↗
10. Fast dataset search with Earth Mover’s Distance10.14778/3551793.3551811 ↗
11. Backurs, A., Dong, Y., Indyk, P., Razenshteyn, I., and Wagner, T. (2020, January 12–18). Scalable nearest neighbor search for optimal transport. Proceedings of the 37th International Conference on Machine Learning (ICML), Virtual Conference.
12. Spatial keyword search: A survey10.1007/s10707-019-00373-y ↗
13. Task: An efficient framework for instant error-tolerant spatial keyword queries on road networks10.14778/3603581.3603584 ↗
14. Luo, C., Jin, L., Liu, Q., Gao, Y., and Chen, L. (2024, January 13–16). TASKS: A Real-Time Query System for Instant Error-Tolerant Spatial Keyword Queries on Road Networks. Proceedings of the IEEE 40th International Conference on Data Engineering (ICDE), Utrecht, The Netherlands.10.1109/ICDE60146.2024.00415 ↗
15. Efficient processing of moving collective spatial keyword queries10.1007/s00778-019-00583-8 ↗
16. Jin, J., An, N., and Sivasubramaniam, A. (March, January 29). Analyzing range queries on spatial data. Proceedings of the 16th International Conference on Data Engineering (ICDE), San Diego, CA, USA.
17. Zacharatou, E.T., Šidlauskas, D., Tauheed, F., Heinis, T., and Ailamaki, A. (2019, January 16–20). Efficient bundled spatial range queries. Proceedings of the 27th ACM SIGSPATIAL International Conference on Advances in Geographic Information Systems (SIGSPATIAL), Long Beach, CA, USA.10.1145/3347146.3359077 ↗
18. Li, Z., Dai, H., Sun, J., Zhou, H., Li, P., and Yang, G. (2024, January 13–15). ESDRS: Efficient Spatial Dataset Range Search Processing. Proceedings of the 26th IEEE International Conference on High Performance Computing, Communications and Systems (HPCC), Wuhan, China.
19. Exemplar queries: Give me an example of what you need10.14778/2732269.2732273 ↗
20. DICE: Data discovery by example10.14778/3476311.3476353 ↗
21. Wang, S., Bao, Z., Culpepper, J.S., Sellis, T., Sanderson, M., and Qin, X. (2017, January 19–22). Answering top-k exemplar trajectory queries. Proceedings of the 33rd IEEE International Conference on Data Engineering (ICDE), San Diego, CA, USA.10.1109/ICDE.2017.114 ↗
22. Exemplar queries: A new way of searching10.1007/s00778-016-0429-2 ↗
23. Li, P., Dai, H., Wang, S., Yang, W., and Yang, G. (2024, January 21–25). Privacy-preserving Spatial Dataset Search in Cloud. Proceedings of the 33rd ACM International Conference on Information and Knowledge Management (CIKM), Birmingham, UK.10.1145/3627673.3679733 ↗
24. Mottin, D., Lissandrini, M., Velegrakis, Y., and Palpanas, T. (2014, January 22–27). Searching with XQ: The exemplar query search engine. Proceedings of the 2014 ACM SIGMOD International Conference on Management of Data (SIGMOD), Snowbird, UT, USA.10.1145/2588555.2594529 ↗
25. Cao, C., and Li, M. (2021, January 14–18). Generating mobility trajectories with retained data utility. Proceedings of the 27th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (SIGKDD), Virtual Conference.10.1145/3447548.3467158 ↗