Full Citation

Title: Querying a Collection of Continuous Functions

Citation Type: Journal Article

Publication Year: 2018

ISBN:

ISSN:

DOI:

NSFID:

PMCID:

PMID:

Abstract: 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 subdomain, 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 query processing costs.

Url: http://ieeexplore.ieee.org/abstract/document/8283622/?reload=true

User Submitted?: No

Authors: Yang, Guolei; Cai, Ying

Periodical (Full): IEEE Transactions on Knowledge and Data Engineering

Issue: 9

Volume: 30

Pages: 1783-1795

Data Collections: IPUMS USA

Topics: Methodology and Data Collection, Other

Countries: