Databases (cs.DB)

  • PDF
    The paper presents a novel concept that analyzes and visualizes worldwide fashion trends. Our goal is to reveal cutting-edge fashion trends without displaying an ordinary fashion style. To achieve the fashion-based analysis, we created a new fashion culture database (FCDB), which consists of 76 million geo-tagged images in 16 cosmopolitan cities. By grasping a fashion trend of mixed fashion styles,the paper also proposes an unsupervised fashion trend descriptor (FTD) using a fashion descriptor, a codeword vetor, and temporal analysis. To unveil fashion trends in the FCDB, the temporal analysis in FTD effectively emphasizes consecutive features between two different times. In experiments, we clearly show the analysis of fashion trends and fashion-based city similarity. As the result of large-scale data collection and an unsupervised analyzer, the proposed approach achieves world-level fashion visualization in a time series. The code, model, and FCDB will be publicly available after the construction of the project page.
  • PDF
    Many efforts have been dedicated to identifying restrictions on ontologies expressed as tuple-generating dependencies (tgds), a.k.a. existential rules, that lead to the decidability for the problem of answering ontology-mediated queries (OMQs). This has given rise to three families of formalisms: guarded, non-recursive, and sticky sets of tgds. In this work, we study the containment problem for OMQs expressed in such formalisms, which is a key ingredient for solving static analysis tasks associated with them. Our main contribution is the development of specially tailored techniques for OMQ containment under the classes of tgds stated above. This enables us to obtain sharp complexity bounds for the problems at hand. We also apply our techniques to pinpoint the complexity of problems associated with two emerging applications of OMQ containment: distribution over components and UCQ rewritability of OMQs.
  • PDF
    We study changes in metrics that are defined on a cartesian product of trees. Such metrics occur naturally in many practical applications, where a global metric (such as revenue) can be broken down along several hierarchical dimensions (such as location, gender, etc). Given a change in such a metric, our goal is to identify a small set of non-overlapping data segments that account for the change. An organization interested in improving the metric can then focus their attention on these data segments. Our key contribution is an algorithm that mimics the operation of a hierarchical organization of analysts. The algorithm has been successfully applied, for example within Google Adwords to help advertisers triage the performance of their advertising campaigns. We show that the algorithm is optimal for two dimensions, and has an approximation ratio $\log^{d-2}(n+1)$ for $d \geq 3$ dimensions, where $n$ is the number of input data segments. For the Adwords application, we can show that our algorithm is in fact a $2$-approximation. Mathematically, we identify a certain data pattern called a \emphconflict that both guides the design of the algorithm, and plays a central role in the hardness results. We use these conflicts to both derive a lower bound of $1.144^{d-2}$ (again $d\geq3$) for our algorithm, and to show that the problem is NP-hard, justifying the focus on approximation.