enter search term and/or author name
Classification of annotation semirings over containment of conjunctive queries
Egor V. Kostylev, Juan L. Reutter, András Z. Salamon
Article No.: 1
We study the problem of query containment of conjunctive queries over annotated databases. Annotations are typically attached to tuples and represent metadata, such as probability, multiplicity, comments, or provenance. It is usually assumed that...
Database queries can be broadly classified into two categories: reporting queries and aggregation queries. The former retrieves a collection of records from the database that match the query's conditions, while the latter returns an aggregate,...
Pufferfish: A framework for mathematical privacy definitions
Daniel Kifer, Ashwin Machanavajjhala
Article No.: 3
In this article, we introduce a new and general privacy framework called Pufferfish. The Pufferfish framework can be used to create new privacy definitions that are customized to the needs of a given application. The goal of Pufferfish is to allow...
Graph pattern matching is finding all matches in a data graph for a given pattern graph and is often defined in terms of subgraph isomorphism, an
Oblivious bounds on the probability of boolean functions
Wolfgang Gatterbauer, Dan Suciu
Article No.: 5
This article develops upper and lower bounds for the probability of Boolean functions by treating multiple occurrences of variables as independent and assigning them new individual probabilities. We call this approach dissociation and give...
Mining order-preserving submatrices from probabilistic matrices
Qiong Fang, Wilfred Ng, Jianlin Feng, Yuliang Li
Article No.: 6
Order-preserving submatrices (OPSMs) capture consensus trends over columns shared by rows in a data matrix. Mining OPSM patterns discovers important and interesting local correlations in many real applications, such as those involving...
Extending string similarity join to tolerant fuzzy token matching
Jiannan Wang, Guoliang Li, Jianhua Feng
Article No.: 7
String similarity join that finds similar string pairs between two string sets is an essential operation in many applications and has attracted significant attention recently in the database community. A significant challenge in similarity join is...
Deletion without rebalancing in multiway search trees
Siddhartha Sen, Robert E. Tarjan
Article No.: 8
Some database systems that use a form of B-tree for the underlying data structure do not do rebalancing on deletion. This means that a bad sequence of deletions can create a very unbalanced tree. Yet such databases perform well in practice....
Efficient range searching for categorical and plain data
Article No.: 9
In the orthogonal range-searching problem, we store a set of input points S in a data structure; the answer to a query Q is a piece of information about points in Q∩S, for example, the list of all points in...