[Profile picture of Ruben Verborgh]

Ruben Verborgh

A File-Based Linked Data Fragments Approach to Prefix Search

Dedecker Ruben, Harm Delva, Pieter Colpaert, and Ruben Verborgh

Text-fields that need to look up specific entities in a dataset can be equipped with autocompletion functionality. When a dataset becomes too large to be embedded in the page, setting up a full-text search API is not the only alternative. Alternate API designs that balance different trade-offs such as archivability, cacheability and privacy, may not require setting up a new back-end architecture. In this paper, we propose to perform prefix search over a fragmentation of the dataset, enabling the client to take part in the query execution by navigating through the fragmented dataset. Our proposal consists of (i) a self-describing fragmentation strategy, (ii) a client search algorithm, and (iii) an evaluation of the proposed solution, based on a small dataset of 73k entities and a large dataset of 3.87 m entities. We found that the server cache hit ratio is three times higher compared to a server-side prefix search API, at the cost of a higher bandwidth consumption. Nevertheless, an acceptable user-perceived performance has been measured: assuming 150 ms as an acceptable waiting time between keystrokes, this approach allows 15 entities per prefix to be retrieved in this interval. We conclude that an alternate set of trade-offs has been established for specific prefix search use cases: having added more choice to the spectrum of Web APIs for autocompletion, a file-based approach enables more datasets to afford prefix search.

full text BibTeX other citation formats

Published in 2021 in Proceedings of the 21th International Conference on Web Engineering.

Keywords:

Read this article online

Cite this article in your work

Cite this article easily using its BibTeX entry: 

@inproceedings{dedecker_icwe_2021,
  author = {Ruben, Dedecker and Delva, Harm and Colpaert, Pieter and Verborgh, Ruben},
  title = {A File-Based {Linked Data Fragments} Approach to Prefix Search},
  booktitle = {Proceedings of the 21th International Conference on Web Engineering},
  editor = {Brambilla, Marco and Chbeir, Richard and Frasincar, Flavius and Manolescu, Ioana},
  year = 2021,
  month = may,
  pages = {53--67},
  series = {Lecture Notes in Computer Science},
  volume = 12840,
  publisher = {Springer},
  url = {https://link.springer.com/chapter/10.1007/978-3-030-74296-6_5},
  doi = {10.1007/978-3-030-74296-6_5},
}

Alternatively, pick a reference of your choice below:

ACM
Dedecker Ruben, Harm Delva, Pieter Colpaert, and Ruben Verborgh. 2021. A File-Based Linked Data Fragments Approach to Prefix Search. In Proceedings of the 21th International Conference on Web Engineering (Lecture Notes in Computer Science), Springer, 53–67.
APA
Ruben, D., Delva, H., Colpaert, P., & Verborgh, R. (2021). A File-Based Linked Data Fragments Approach to Prefix Search. In M. Brambilla, R. Chbeir, F. Frasincar, & I. Manolescu (Eds.), Proceedings of the 21th International Conference on Web Engineering (Vol. 12840, pp. 53–67). Springer.
IEEE
D. Ruben, H. Delva, P. Colpaert, and R. Verborgh, “A File-Based Linked Data Fragments Approach to Prefix Search,” in Proceedings of the 21th International Conference on Web Engineering, 2021, vol. 12840, pp. 53–67.
LNCS
Ruben, D., Delva, H., Colpaert, P., Verborgh, R.: A File-Based Linked Data Fragments Approach to Prefix Search. In: Brambilla, M., Chbeir, R., Frasincar, F., and Manolescu, I. (eds.) Proceedings of the 21th International Conference on Web Engineering. pp. 53–67. Springer (2021).
MLA
Ruben, Dedecker, et al. “A File-Based Linked Data Fragments Approach to Prefix Search.” Proceedings of the 21th International Conference on Web Engineering, edited by Marco Brambilla et al., vol. 12840, Springer, 2021, pp. 53–67.

Discuss this article