Querying a Collection of Continuous Functions
| Autor: | Guolei Yang, Ying Cai |
|---|---|
| Rok vydání: | 2018 |
| Předmět: |
Theoretical computer science
Computational Theory and Mathematics Computer science 020204 information systems Search engine indexing Scalar (mathematics) 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 02 engineering and technology Data structure Computer Science Applications Information Systems |
| Zdroj: | IEEE Transactions on Knowledge and Data Engineering. 30:1783-1795 |
| ISSN: | 2326-3865 1041-4347 |
| DOI: | 10.1109/tkde.2018.2802936 |
| Popis: | We introduce a new query primitive called Function Query (FQ). An FQ operates on a set of math functions and retrieves the functions whose output with a given input satisfies a query condition (e.g., being among top k, within a given range). While FQ finds its natural uses in querying a database of math functions, it can also be applied on a database of discrete values. We show that by interpreting the database as a set of user-defined functions, FQ can achieve the same functionality as existing analytic queries such as top-k query and scalar product query. We address the challenge of efficient execution of FQ. The core of our solution is a novel data structure called Intersection-tree . Our research takes advantage of the fact that 1) the intersections of a set of continuous functions partition their domain into a number of subdomains , and 2) in each of these subdomains, the functions can be sorted based on their output. We evaluate the performance of the proposed techniques through analysis, prototyping, and experiments using both synthetic and real-world data. When querying a database of functions, our techniques scale well. When applied on a database of discrete values, our techniques are more versatile and outperform existing techniques in terms of various performance metrics. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|