Differentially private graph analysis is a powerful tool for deriving insights from diverse graph data while protecting individual information. Designing private analytic algorithms for different graph queries often requires starting from scratch. In contrast, differentially private synthetic graph generation offers a general paradigm that supports one-time generation for multiple queries. Although various differentially private graph generation algorithms have been proposed, comparing them effectively remains challenging due to various factors, including differing privacy definitions, diverse graph datasets, varied privacy requirements, and multiple utility metrics. To this end, we propose PGB (Private Graph Benchmark), a comprehensive benchmark designed to enable researchers to compare differentially private graph generation algorithms fairly. We begin by identifying four essential elements of existing works as a 4-tuple: mechanisms, graph datasets, privacy requirements, and utility metrics. We discuss principles regarding these elements to ensure the comprehensiveness of a benchmark. Next, we present a benchmark instantiation that adheres to all principles, establishing a new method to evaluate existing and newly proposed graph generation algorithms. Through extensive theoretical and empirical analysis, we gain valuable insights into the strengths and weaknesses of prior algorithms. Our results indicate that there is no universal solution for all possible cases. Finally, we provide guidelines to help researchers select appropriate mechanisms for various scenarios.

Differentially private triangle counting in graphs is essential for analyzing connection patterns and calculating clustering coefficients while protecting sensitive individual information. Previous works have relied on either central or local models to enforce differential privacy. However, a significant utility gap exists between the central and local models of differentially private triangle counting, depending on whether or not a trusted server is needed. In particular, the central model provides a high accuracy but necessitates a trusted server. The local model does not require a trusted server but suffers from limited accuracy. Our paper introduces a crypto-assisted differentially private triangle counting system, named CARGO, leveraging cryptographic building blocks to improve the effectiveness of differentially private triangle counting without assumption of trusted servers. It achieves high utility similar to the central model but without the need for a trusted server like the local model. CARGO consists of three main components. First, we introduce a similarity-based projection method that reduces the global sensitivity while preserving more triangles via triangle homogeneity. Second, we present a triangle counting scheme based on the additive secret sharing that securely and accurately computes the triangles while protecting sensitive information. Third, we design a distributed perturbation algorithm that perturbs the triangle count with minimal but sufficient noise. We also provide a comprehensive theoretical and empirical analysis of our proposed methods. Extensive experiments demonstrate that our CARGO significantly outperforms the local model in terms of utility and achieves high-utility triangle counting comparable to the central model.

Differentially Private Federated Learning (DP-FL) has garnered attention as a collaborative machine learning approach that ensures formal privacy. Most DP-FL approaches ensure DP at the record-level within each silo for cross-silo FL. However, a single user's data may extend across multiple silos, and the desired user-level DP guarantee for such a setting remains unknown. In this study, we present Uldp-FL, a novel FL framework designed to guarantee user-level DP in cross-silo FL where a single user's data may belong to multiple silos. Our proposed algorithm directly ensures user-level DP through per-user weighted clipping, departing from group-privacy approaches. We provide a theoretical analysis of the algorithm's privacy and utility. Additionally, we improve the utility of the proposed algorithm with an enhanced weighting strategy based on user record distribution and design a novel private protocol that ensures no additional information is revealed to the silos and the server. Experiments on real-world datasets show substantial improvements in our methods in privacy-utility trade-offs under user-level DP compared to baseline methods. To the best of our knowledge, our work is the first FL framework that effectively provides user-level DP in the general cross-silo FL setting.

Human mobility data offers valuable insights for many applications such as urban planning and pandemic response, but its use also raises privacy concerns. In this paper, we introduce the Hierarchical and Multi-Resolution Network (HRNet), a novel deep generative model specifically designed to synthesize realistic human mobility data while guaranteeing differential privacy. We first identify the key difficulties inherent in learning human mobility data under differential privacy. In response to these challenges, HRNet integrates three components: a hierarchical location encoding mechanism, multi-task learning across multiple resolutions, and private pre-training. These elements collectively enhance the model's ability under the constraints of differential privacy. Through extensive comparative experiments utilizing a real-world dataset, HRNet demonstrates a marked improvement over existing methods in balancing the utility-privacy trade-off.

Time is an important aspect of documents and is used in a range of NLP and IR tasks. In this work, we investigate methods for incorporating temporal information during pre-training to further improve the performance on time-related tasks. Compared with common pre-trained language models like BERT which utilize synchronic document collections (e.g., BookCorpus and Wikipedia) as the training corpora, we use long-span temporal news article collection for building word representations. We introduce BiTimeBERT, a novel language representation model trained on a temporal collection of news articles via two new pre-training tasks, which harnesses two distinct temporal signals to construct time-aware language representations. The experimental results show that BiTimeBERT consistently outperforms BERT and other existing pre-trained models with substantial gains on different downstream NLP tasks and applications for which time is of importance (e.g., the accuracy improvement over BERT is 155% on the event time estimation task).

Combining Federated Learning (FL) with a Trusted Execution Environment (TEE) is a promising approach for realizing privacy-preserving FL, which has garnered significant academic attention in recent years. Implementing the TEE on the server side enables each round of FL to proceed without exposing the client's gradient information to untrusted servers. This addresses usability gaps in existing secure aggregation schemes as well as utility gaps in differentially private FL. However, to address the issue using a TEE, the vulnerabilities of server-side TEEs need to be considered---this has not been sufficiently investigated in the context of FL. The main technical contribution of this study is the analysis of the vulnerabilities of TEE in FL and the defense. First, we theoretically analyze the leakage of memory access patterns, revealing the risk of sparsified gradients, which are commonly used in FL to enhance communication efficiency and model accuracy. Second, we devise an inference attack to link memory access patterns to sensitive information in the training dataset. Finally, we propose an oblivious yet efficient aggregation algorithm to prevent memory access pattern leakage. Our experiments on real-world data demonstrate that the proposed method functions efficiently in practical scales.

The Shapley value (SV) is a fair and principled metric for contribution evaluation in cross-silo federated learning (cross-silo FL), wherein organizations, i.e., clients, collaboratively train prediction models with the coordination of a parameter server. However, existing SV calculation methods for FL assume that the server can access the raw FL models and public test data. This may not be a valid assumption in practice considering the emerging privacy attacks on FL models and the fact that test data might be clients' private assets. Hence, we investigate the problem of secure SV calculation for cross-silo FL. We first propose HESV , a one-server solution based solely on homomorphic encryption (HE) for privacy protection, which has limitations in efficiency. To overcome these limitations, we propose SecSV , an efficient two-server protocol with the following novel features. First, SecSV utilizes a hybrid privacy protection scheme to avoid ciphertext-ciphertext multiplications between test data and models, which are extremely expensive under HE. Second, an efficient secure matrix multiplication method is proposed for SecSV. Third, SecSV strategically identifies and skips some test samples without significantly affecting the evaluation accuracy. Our experiments demonstrate that SecSV is 7.2--36.6× as fast as HESV, with a limited loss in the accuracy of calculated SVs.

Although differentially private streaming data release has been studied extensively, how to strike a good balance between privacy and utility on correlated data is still an open problem. Many existing works focus on enhancing privacy when applying differential privacy to correlated data. They show that differential privacy may suffer extra privacy leakage under correlations, and it is inevitable to resort to a small privacy budget to prevent such privacy leakage. However, there is no attempt to solve the consequential utility problem. In this work, for the first time, we propose a post-processing framework to boost the utility of differential privacy data release under temporal correlations. Specifically, we model the problem as a maximum posterior estimation given the released differentially private data and correlation model. We finally transform this problem into a nonlinear constrained programming. Our experiments demonstrate the effectiveness of the proposed approach where the utility and accuracy of differentially private data are significantly improved by nearly ten times in terms of mean square error when a strict privacy budget is given.

Publishing graph statistics under node differential privacy has attracted much attention since it provides a stronger privacy guarantee than edge differential privacy. Existing works related to node differential privacy assume a trusted data curator who holds the whole graph. However, in many applications, a trusted curator is usually not available due to privacy and security issues. In this paper, for the first time, we investigate the problem of publishing graph statistics under Node Local Differential privacy (Node-LDP), which does not rely on a trusted server. We propose an algorithm to publish the degree distribution with Node-LDP by exploring how to select the graph projection parameter in the local setting and how to execute the graph projection locally. Specifically, we propose a crypto-assisted local projection method based on cryptographic primitives, achieving the higher accuracy than our baseline pureLDP local projection method. Furthermore, we improve our baseline graph projection method from node-level to edge-level that preserves more neighboring information, owning better utility. Finally, extensive experiments on real-world graphs show that crypto-assisted parameter selection owns better utility than pureLDP parameter selection, and edge-level local projection provides higher accuracy than node-level local projection, improving by up to 57.2% and 79.8%, respectively.

Differential privacy (DP) is attracting considerable research attention as a privacy definition when publishing statistics of a dataset. This study focused on addressing the limitation that DP inevitably causes two-sided errors. For example, consider a threshold query that asks whether a counting is above a given threshold or not. An answer through the DP mechanism can cause error. This phenomenon is not desirable for sensitive analysis such as the counting of COVID-19-infected individuals (in a dataset) visiting a specific location; misinformation can result in incorrect decision-making which can increase the epidemic. To the best of our knowledge, the problem is yet to be solved. We proposed a variation of DP, namely asymmetric DP (ADP) to solve the problem. ADP can provide reasonable privacy protection and achieve one-sided errors. Finally, experiments were conducted to evaluate the utility of the proposed mechanism for the epidemic analysis using a real-world dataset. The results of study revealed the feasibility of proposed mechanisms.

Acquiring a sufficient amount of training data is a significant bottleneck for machine learning (ML) based data analytics. Recently, commoditizing ML models has been proposed as an economical and moderate solution to ML-oriented data acquisition. However, existing model marketplaces assume that the broker can access data owners’ private training data, which may not be realistic in practice. In this paper, to promote trustworthy data acquisition for ML tasks, we propose FL-Market, a locally private model marketplace that protects privacy against not only model buyers but also an untrusted broker. FL-Market decouples ML from the need to centrally gather training data on the broker’s side using federated learning, a privacy-preserving ML paradigm in which data owners collaboratively train an ML model by uploading local gradients (to be aggregated into a global gradient for model updating). Then, FL-Market enables data owners to locally perturb their gradients by local differential privacy and thus further prevents privacy risks. To drive FL-Market, we propose a deep learning-empowered auction mechanism for intelligently deciding the local gradients’ perturbation levels and an optimal aggregation mechanism for aggregating the perturbed gradients. Our auction and aggregation mechanisms can jointly maximize the global gradient’s accuracy, which optimizes model buyers’ utility. Our experiments verify the effectiveness of the proposed mechanisms.

In the last few years, open-domain question answering (ODQA) has advanced rapidly due to the development of deep learning techniques and the availability of large-scale QA datasets. However, the current datasets are essentially designed for synchronic document collections (e.g., Wikipedia). Temporal news collections such as long-term news archives spanning decades are rarely used in training the models despite they are quite valuable for our society. To foster the research in the field of ODQA on such historical collections, we present ArchivalQA, a large question answering dataset consisting of 532,444 question-answer pairs which is designed for temporal news QA. We divide our dataset into four subparts based on the question difficulty levels and the containment of temporal expressions, which we believe are useful for training and testing ODQA systems characterized by different strengths and abilities. The novel QA dataset-constructing framework that we introduce can be also applied to generate high-quality, non-ambiguous questions over other types of temporal document collections.

Recently, it is shown that shuffling can amplify the central differential privacy guarantees of data randomized with local differential privacy. Within this setup, a centralized, trusted shuffler is responsible for shuffling by keeping the identities of data anonymous, which subsequently leads to stronger privacy guarantees for systems. However, introducing a centralized entity to the originally local privacy model loses some appeals of not having any centralized entity as in local differential privacy. Moreover, implementing a shuffler in a reliable way is not trivial due to known security issues and/or requirements of advanced hardware or secure computation technology.

How can we explore the unknown properties of high-dimensional sensitive relational data while preserving privacy? We study how to construct an explorable privacy-preserving materialized view under differential privacy. No existing state-of-the-art methods simultaneously satisfy the following essential properties in data exploration: workload independence, analytical reliability (i.e., providing error bound for each search query), applicability to high-dimensional data, and space efficiency. To solve the above issues, we propose HDPView, which creates a differentially private materialized view by well-designed recursive bisected partitioning on an original data cube, i.e., count tensor. Our method searches for block partitioning to minimize the error for the counting query, in addition to randomizing the convergence, by choosing the effective cutting points in a differentially private way, resulting in a less noisy and compact view. Furthermore, we ensure formal privacy guarantee and analytical reliability by providing the error bound for arbitrary counting queries on the materialized views. HDPView has the following desirable properties: (a) Workload independence , (b) Analytical reliability , (c) Noise resistance on high-dimensional data , (d) Space efficiency. To demonstrate the above properties and the suitability for data exploration, we conduct extensive experiments with eight types of range counting queries on eight real datasets. HDPView outperforms the state-of-the-art methods in these evaluations.

How can we release a massive volume of sensitive data while mitigating privacy risks? Privacy-preserving data synthesis enables the data holder to outsource analytical tasks to an untrusted third party. The state-of-the-art approach for this problem is to build a generative model under differential privacy, which offers a rigorous privacy guarantee. However, the existing method cannot adequately handle high dimensional data. In particular, when the input dataset contains a large number of features, the existing techniques require injecting a prohibitive amount of noise to satisfy differential privacy, which results in the outsourced data analysis meaningless. To address the above issue, this paper proposes privacy-preserving phased generative model (P3GM), which is a differentially private generative model for releasing such sensitive data. P3GM employs the two-phase learning process to make it robust against the noise, and to increase learning efficiency (e.g., easy to converge). We give theoretical analyses about the learning complexity and privacy loss in P3GM. We further experimentally evaluate our proposed method and demonstrate that P3GM significantly outperforms existing solutions. Compared with the state-of-the-art methods, our generated samples look fewer noises and closer to the original data in terms of data diversity. Besides, in several data mining tasks with synthesized data, our model outperforms the competitors in terms of accuracy.

Real world events are quite often mentioned in texts. Estimating the occurrence time of event mentions has many applications in IR, QA, general document understanding and downstream NLP tasks. In this paper we propose an approach to temporal profiling of event mentions in text. Our method utilizes a news article archival collection for collecting temporal as well as textual information containing contemporary and retrospective event references. As we demonstrate in our experiments, the recent method which relies on secondary data sources like Wikipedia is insufficient to correctly estimate the event time, especially, for minor or less well-known events that happened in the past. Our method then harnesses news article archives to effectively infer the occurrence time of past events, and is able to estimate the time at different temporal granularities (e.g., day, week, month, or year). As evidenced through extensive experiments, the proposed model outperforms the existing methods by a large margin at all granularities. We also demonstrate that our approach helps to answer arbitrary questions about past events, when incorporated into a QA framework operating over news article archives.

Location privacy-preserving mechanisms (LPPMs) have been extensively studied for protecting users' location privacy by releasing a perturbed location to third parties such as location-based service providers. However, when a user's perturbed locations are released continuously, existing LPPMs may not protect the sensitive information about the user's real-world activities, such as “visited hospital in the last week” or “regularly commuting between location A and location B every weekday” (it is easy to infer that location A and location B may be home and office), which we call it spatiotemporal event. In this paper, we first formally define spatiotemporal event as Boolean expressions between location and time predicates, and then we define ε-spatiotemporal event privacy by extending the notion of differential privacy. Second, to understand how much spatiotemporal event privacy that existing LPPMs can provide, we design computationally efficient algorithms to quantify the spatiotemporal event privacy leakage of state-of-the-art LPPMs. It turns out that the existing LPPMs may not adequately protect spatiotemporal event privacy. Third, we propose a framework, PriSTE, to transform an existing LPPM into one protecting spatiotemporal event privacy by calibrating the LPPM's privacy budgets. Our experiments on real-life and synthetic data verified that the proposed method is effective and efficient.

The COVID-19 pandemic has prompted techno-logical measures to control the spread of the disease. Private contact tracing (PCT) is a promising technique for this purpose. However, the recently proposed Bluetooth-based PCT has several limitations in terms of functionality and flexibility. The existing systems are only able to detect direct contact (i.e., human-human contact) but cannot detect indirect contact (i.e., human-object, such as disease transmission through a surface). Moreover, the rule of risky contact cannot be flexibly changed with the environmental situation and the nature of the virus. In this paper, we propose a secure and efficient trajectory-based PCT system using trusted hardware. We formalize trajectory-based PCT as a generalization of the well-studied private set intersection (PSI), which is mostly based on cryptographic primitives and is thus insufficient. We solve the problem by leveraging trusted hardware such as Intel SGX and designing a novel algorithm to achieve a secure, efficient and flexible PCT system. Our experiments on real-world data show that the proposed system can achieve high performance and scalability. Specifically, our system (one single machine with Intel SGX) can process thousands of queries on 100 million records of trajectory data in a few seconds.

As personal data has been the new oil of the digital era, there is a growing trend perceiving personal data as a commodity. Existing studies have built theories on how to map the privacy loss to an arbitrage-free price. They assumed that a data buyer could purchase arbitrarily accurate results as long as she could compensate data owners for their privacy loss. However, it may not be a viable business model under strict privacy regulations, such as GDPR and CCPA, and data owners' emerging privacy concerns. In this paper, we study how to empower data owners with the control of privacy loss when continuously trading their personal mobile data. Concretely, we propose a framework for trading infinite streaming mobile data which enables each data owner to bound her privacy loss in a w-length sliding window. Introducing such upper bounds of privacy loss makes the existing trading frameworks invalid and raises new technical challenges in terms of budget allocation and arbitrage-free pricing. To address these problems, we propose a modularized trading framework with instances that allows data owners to personalize their privacy loss while the price is still arbitrage-free. Finally, we conduct experiments to verify the effectiveness of the proposed trading protocols.

A significant number of old photographs including ones that are posted online do not contain the information of the date at which they were taken, or this information needs to be verified. Many of such pictures are either scanned analog photographs or photographs taken using a digital camera with incorrect settings. Estimating the date of such pictures is useful for enhancing data quality and its consistency, improving information retrieval and for other related applications. In this study, we propose a novel approach for automatic estimation of the shooting dates of photographs based on a rank-consistent ordinal classification method for neural networks. We also introduce an ensemble approach that involves object segmentation. We conclude that assuring the rank consistency in the ordinal classification as well as combining models trained on segmented objects improve the results of the age determination task.

In this demonstration, we present a privacy-preserving epidemic surveillance system. Recently, many countries that suffer from COVID-19 crises attempt to access citizen's location data to eliminate the outbreak. However, it raises privacy concerns and may open the doors to more invasive forms of surveillance in the name of public health. It also brings a challenge for privacy protection techniques: how can we leverage people's mobile data to help combat the pandemic without scarifying location privacy. We demonstrate that we can achieve this by implementing policy-based location privacy for epidemic surveillance. Our system has three primary functions for epidemic surveillance: people flow monitoring, epidemic analysis, and contact tracing. We provide an interactive tool allowing the attendees to explore and examine the usability of our system: (1) the utility of location monitor and disease transmission model estimation, (2) the procedure of contact tracing in our systems, and (3) the privacy-utility trade-offs w.r.t. different policy graphs. The attendees will find that we can have the high usability for epidemic surveillance while preserving location privacy.

To obtain accurate information through web searches, people have to search for information carefully. This study investigates how the search behaviors and decision outcomes of searchers were affected by the documents they encountered during their search process. We focus on two document factors: (1) opinion (consistent and inconsistent) with the searchers' beliefs prior to the search task, and (2) credibility (high and low). We conducted a user study in which 260 participants were asked to perform health-related search tasks while controlling a search result with different opinions and credibility levels. The results revealed that (i) the participants spent more effort searching by issuing more queries, when belief-inconsistent documents were presented; (ii) the documents' opinion and credibility affected their belief dynamics, (i.e., how their beliefs changed after the search task); and (iii) their belief dynamics and search efforts had few relationships. These findings suggest that search engines could prevent users from polarization and thus, help them to obtain accurate information, by presenting documents that are inconsistent with users' beliefs on the higher-rank of the results.

We propose a method for identifying a set of entity properties from text. Identifying entity properties is similar to a relation extraction task that can be cast as a classification of sentences. Normally, this task can be achieved by distant supervised learning by automatically preparing training sentences for each property; however, it is impractical to prepare training sentences for every property. Therefore, we describe a zero-shot learning problem for this task and propose a neural network-based model that does not rely on a complete training set comprising training sentences for every property. To achieve this, we utilize embeddings of properties obtained from a knowledge graph embedding using different components of a knowledge graph structure. The embeddings of properties are combined with the model to enable identification of properties with no available training sentences. By using our newly constructed dataset as well as an existing dataset, experiments revealed that our model achieved a better performance for properties with no training sentences, relative to baseline results, even comparable to that achieved for properties with training sentences.

Abstract We propose a novel way of utilizing and accessing information stored in news archives as well as a new style of investigating the history. Our idea is to automatically generate similar entity pairs given two sets of entities, one from the past and one representing the present. This allows performing entity-oriented mapping between different times. We introduce an effective method to solve the aforementioned task based on a concise integer linear programming framework. In particular, our model first conducts typicality analysis to estimate entity representativeness. It next constructs orthogonal transformation between the two entity collections. The result is a set of typical across-time comparables. We demonstrate the effectiveness of our approach on the New York Times dataset through both qualitative and quantitative tests.

Location privacy-preserving mechanisms (LPPMs) have been extensively studied for protecting a user's location in location-based services. However, when user's perturbed locations are released continuously, existing LPPMs may not protect users' sensitive spatiotemporal event , such as "visited hospital in the last week" or "regularly commuting between location 1 and location 2 every morning and afternoon" (it is easy to infer that locations 1 and 2 may be home and office). In this demonstration, we demonstrate PriSTE for protecting spatiotemporal event privacy in continuous location release. First, to raise users' awareness of such a new privacy goal, we design an interactive tool to demonstrate how accurate an adversary could infer a secret spatiotemporal event from a sequence of locations or even LPPM-protected locations. The attendees can find that some spatiotemporal events are quite risky and even these state-of-the-art LPPMs do not always protect spatiotemporal event privacy. Second, we demonstrate how a user can use PriSTE to automatically or manually convert an LPPM for location privacy into one protecting spatiotemporal event privacy in continuous location-based services. Finally, we visualize the trade-off between privacy and utility so that users can choose appropriate privacy parameters in different application scenarios.

Differential Privacy (DP) has received increasing attention as a rigorous privacy framework. Many existing studies employ traditional DP mechanisms (e.g., the Laplace mechanism) as primitives to continuously release private data for protecting privacy at each time point (i.e., event-level privacy), which assume that the data at different time points are independent, or that adversaries do not have knowledge of correlation between data. However, continuously generated data tend to be temporally correlated, and such correlations can be acquired by adversaries. In this paper, we investigate the potential privacy loss of a traditional DP mechanism under temporal correlations. First, we analyze the privacy leakage of a DP mechanism under temporal correlation that can be modeled using Markov Chain. Our analysis reveals that, the event-level privacy loss of a DP mechanism may increase over time. We call the unexpected privacy loss temporal privacy leakage (TPL). Although TPL may increase over time, we find that its supremum may exist in some cases. Second, we design efficient algorithms for calculating TPL. Third, we propose data releasing mechanisms that convert any existing DP mechanism into one against TPL. Experiments confirm that our approach is efficient and effective.

Presents revisions to the above named paper.

In many real-world systems, such as Internet of Thing, sensitive data streams are collected and analyzed continually. To protect privacy, a number of mechanisms are designed to achieve ϵ-differential privacy for processing sensitive streaming data, whose privacy loss is considered to be rigorously controlled within a given parameter ϵ . However, most of the existing studies do not consider the effect of temporal correlations among the continuously generated data on the privacy loss. Our recent work reveals that, the privacy loss of a traditional DP mechanism (e.g., Laplace mechanism) may not be bounded by ϵ due to temporal correlations. We call such unexpected privacy loss Temporal Privacy Leakage (TPL). In this demonstration, we design a system, ConTPL, which is able to automatically convert an existing differentially private streaming data release mechanism into one bounding TPL within a specified level. ConTPL also provides an interactive interface and real-time visualization to help data curator to understand and explore the effect of different parameters on TPL.

Differential Privacy (DP) has received increasing attention as a rigorous privacy framework. Many existing studies employ traditional DP mechanisms (e.g., the Laplace mechanism) as primitives, which assume that the data are independent, or that adversaries do not have knowledge of the data correlations. However, continuous generated data in the real world tend to be temporally correlated, and such correlations can be acquired by adversaries. In this paper, we investigate the potential privacy loss of a traditional DP mechanism under temporal correlations in the context of continuous data release. First, we model the temporal correlations using Markov model and analyze the privacy leakage of a DP mechanism when adversaries have knowledge of such temporal correlations. Our analysis reveals that the privacy loss of a DP mechanism may accumulate and increase over time. We call it temporal privacy leakage. Second, to measure such privacy loss, we design an efficient algorithm for calculating it in polynomial time. Although the temporal privacy leakage may increase over time, we also show that its supremum may exist in some cases. Third, to bound the privacy loss, we propose mechanisms that convert any existing DP mechanism into one against temporal privacy leakage. Experiments with synthetic data confirm that our approach is efficient and effective.

We address a new multi-user routing problem: mutually beneficial confluent routing (MCR). In the MCR, every user has his/her own source and destination; confluences of user routes occur so that users can mutually benefit from travelling together on the confluences. The idea of gaining benefit from travelling together is valuable in various practical applications, such as ride sharing, delivery routing, and pedestrian navigation. We formulate the MCR as a new combinatorial optimization problem on road networks to find optimum routes. As the main contributions of this paper [1], we propose exact and efficient algorithms for the MCR for the setting of two or three users. The setting is reasonable for various practical applications. We have the following two difficulties in solving the MCR: (D1) enumerating patterns of how the users meet and part in the MCR; and (D2) searching optimal meeting and parting nodes from numerous nodes. To overcome the difficulty (D1), we ascertain “confluence patterns” of the optimal solutions. Regarding (D2), we propose several efficient node pruning techniques. Experiments done on large scale road networks reveal that our algorithms are sufficiently efficient.

The recent increase in attention to ride-sharing applications demonstrates the importance of routing algorithms for multiple users who obtain benefits from confluence, that is, traveling together on all or part of their routes. We propose novel and flexible formulation of routing optimization for multiple users who have their respective sources and a single common destination. The formulation is general enough to express each user's benefit (or cost) of confluence for every combination of users. Hence, the formulation can represent a wide range of applications and subsumes almost all formulations proposed in literature. We establish an efficient exact method for the formulation. Interestingly, we found well-known Dreyfus-Wagner Algorithm for the Minimum Steiner Tree Problem (MSTP) is extensible for ours, although our formulation is much harder than the MSTP. Our experimental results obtained on large-scale road networks reveal that our method is efficient in practical settings.

We investigate a new multi-user routing problem: mutually beneficial confluent routing (MCR). In the MCR, every user has his/her own source and destination; confluences of user routes occur so that users can mutually benefit from travelling together on the confluences. The idea of gaining benefit from travelling together is valuable in various practical applications, such as ride sharing, delivery routing, and pedestrian navigation. We formulate the MCR as a new combinatorial optimization problem on road networks. The MCR is more general and complex than single vehicle routing problems, ride-sharing problems, and the Steiner tree problem. We propose exact and efficient algorithms for the MCR for the setting of two or three users. The setting is reasonable for various practical applications. The key ideas of our algorithms are to use “confluence patterns” of the optimal solutions and exploit the properties of geometric graphs. Experimental results obtained on large scale road networks reveal that our algorithms are sufficiently efficient.

In contrast to conventional studies of discovering hot spots, by analyzing geo-tagged images on Flickr, we introduce novel methods to discover obscure sightseeing spots that are less well-known while still worth visiting. To this end, we face two new challenges that the classical authority analysis based methods do not encounter: how to discover and rank spots on the basis of 1) popularity (obscurity level) and 2) scenery quality. For the first challenge, we estimate the obscurity level of a spot in accordance with the visiting asymmetry between photographers who are familiar with a target city and those who are not. For the second challenge, the behavior of both viewers who browsed the images and photographers are analyzed per each spot. We also develop an application system to help users to explore sightseeing spots with different geographical granularities. Experimental evaluations and analysis on a real dataset well demonstrate the effectiveness of the proposed methods.

In this paper, we propose and compare three ways of modeling photographers' location familiarity: a social network driven model, a time driven model and a location driven model. Then, the integration of the three models is further discussed. Experimental evaluations and analysis on a real data set consisting of 14,112 images collected from three cities well demonstrate the performance of the proposed classification methods. Many applications could benefit from information about the location familiarity, such as personalized geo-social recommendation, epidemic dispersion, urban computing, and so on.

Recent emerging mobile and wearable technologies make it easy to collect personal spatiotemporal data such as activity trajectories in daily life. Releasing real-time statistics over trajectory streams produced by crowds of people is expected to be valuable for both academia and business, answering questions such as "How many people are in Central Station now?" However, analyzing these raw data will entail risks of compromising individual privacy. ϵ-Differential Privacy has emerged as a de facto standard for private statistics publishing because of its guarantee of being rigorous and mathematically provable. Since user trajectories will be generated infinitely, it is difficult to protect every trajectory under ϵ-differential privacy. To this end, we propose a flexible privacy model of ℓ-trajectory privacy to ensure every length of ℓ trajectories under protection of ϵ-differential privacy. Then we hierarchically design algorithms to satisfy ℓ-trajectory privacy. Experiments using four real-life datasets show that our proposed algorithms are effective and efficient.

Walking is an easy exercise for maintaining health, although there are several environmental factors, such as road congestion or slopes, which are stressful for pedestrians, especially elders. Therefore, a pedestrian navigation system is required to recommend a less stressful route for a user by estimating such environmental factors. Towards realizing such a system, we firstly collect vital sign, spatiotemporal and environmental data from pedestrians, and secondly analyze the relation between them, and then propose models for estimating the personal stress of a pedestrian. As our vital sign data, we calculate the stress of each pedestrian from the R-R interval data obtained by a heart rate sensor. Our spatiotemporal data includes the walking speed of pedestrians and road grade calculated from GPS sensor data. We measure the degree of road congestion, as our environmental data, using a laser range finder. Our analysis reveals that the road congestion is an important factor affecting stress in walking. The proposed models based on neural networks employ the road congestion in addition to the vital sign and spatiotemporal data. Experimental results indicate that the road congestion degree is effective and the stress of pedestrians estimated by our models is similar to the real stress.

Given a huge stream of multiple co-evolving sequences, such as motion capture and web-click logs, how can we find meaningful patterns and spot anomalies? Our aim is to monitor data streams statistically, and find sub sequences that have the characteristics of a given hidden Markov model (HMM). For example, consider an online web-click stream, where massive amounts of access logs of millions of users are continuously generated every second. So how can we find meaningful building blocks and typical access patterns such as weekday/weekend patterns, and also, detect anomalies and intrusions? In this paper, we propose Stream Scan, a fast and exact algorithm for monitoring multiple co-evolving data streams. Our method has the following advantages: (a) it is effective, leading to novel discoveries and surprising outliers, (b) it is exact, and we theoretically prove that Stream Scan guarantees the exactness of the output, (c) it is fast, and requires O (1) time and space per time-tick. Our experiments on 67GB of real data illustrate that Stream Scan does indeed detect the qualifying subsequence patterns correctly and that it can offer great improvements in speed (up to 479,000 times) over its competitors.

While many governments have introduced financial schemes to encourage people to invest, it is difficult to understand investment trusts and decide which one to buy. To address that difficulty of understanding, a method for extracting causalities from monthly reports of investment trusts and visualizing them to support a potential investor's understanding of a trust is proposed. First, CRF is used to extract causalities from monthly reports. Note that features of financial reports other than linguistic features are also considered. Next, a causal network is constructed and visualized in consideration of the degrees of influence, frequency, and newness of the extracted causalities. The LOD control method is then applied to present causalities in consideration of the granularity of events appearing in the causal network. The results of a user evaluation demonstrate that proposed method performed better than a baseline method in terms of helping a user's understanding of investment trusts.

In this paper, we propose a method for assessing quality scores of Wikipedia articles by mutually evaluating editors and texts. Survival ratio based approach is a major approach to assessing article quality. In this approach, when a text survives beyond multiple edits, the text is assessed as good quality, because poor quality texts have a high probability of being deleted by editors. However, many vandals, low quality editors, delete good quality texts frequently, which improperly decreases the survival ratios of good quality texts. As a result, many good quality texts are unfairly assessed as poor quality. In our method, we consider editor quality score for calculating text quality score, and decrease the impact on text quality by vandals. Using this improvement, the accuracy of the text quality score should be improved. However, an inherent problem with this idea is that the editor quality scores are calculated by the text quality scores. To solve this problem, we mutually calculate the editor and text quality scores until they converge. In this paper, we prove that the text quality score converges. We did our experimental evaluation, and confirmed that our proposed method could accurately assess the text quality scores.

We focus on measuring relationships between pairs of objects in Wikipedia whose pages can be regarded as individual objects. Two kinds of relationships between two objects exist: in Wikipedia, an explicit relationship is represented by a single link between the two pages for the objects, and an implicit relationship is represented by a link structure containing the two pages. Some of the previously proposed methods for measuring relationships are cohesion-based methods, which underestimate objects having high degrees, although such objects could be important in constituting relationships in Wikipedia. The other methods are inadequate for measuring implicit relationships because they use only one or two of the following three important factors: distance, connectivity, and cocitation. We propose a new method using a generalized maximum flow which reflects all the three factors and does not underestimate objects having high degree. We confirm through experiments that our method can measure the strength of a relationship more appropriately than these previously proposed methods do. Another remarkable aspect of our method is mining elucidatory objects, that is, objects constituting a relationship. We explain that mining elucidatory objects would open a novel way to deeply understand a relationship.

Given huge collections of time-evolving events such as web-click logs, which consist of multiple attributes (e.g., URL, userID, times- tamp), how do we find patterns and trends? How do we go about capturing daily patterns and forecasting future events? We need two properties: (a) effectiveness, that is, the patterns should help us understand the data, discover groups, and enable forecasting, and (b) scalability, that is, the method should be linear with the data size. We introduce TriMine, which performs three-way mining for all three attributes, namely, URLs, users, and time. Specifically TriMine discovers hidden topics, groups of URLs, and groups of users, simultaneously. Thanks to its concise but effective summarization, it makes it possible to accomplish the most challenging and important task, namely, to forecast future events. Extensive experiments on real datasets demonstrate that TriMine discovers meaningful topics and makes long-range forecasts, which are notoriously difficult to achieve. In fact, TriMine consistently outperforms the best state-of-the-art existing methods in terms of accuracy and execution speed (up to 74x faster).

In this paper, we propose a novel stakeholder mining mechanism for analyzing bias in news articles by comparing descriptions of stakeholders. Our mechanism is based on the presumption that interests often induce bias of news agencies. As we use the term, a ``stakeholder'' is a participant in an event described in a news article who should have some relationships with other participants in the article. Our approach attempts to elucidate bias of articles from three aspects: stakeholders, interests of stakeholders, and the descriptive polarity of each stakeholder. Mining of stakeholders and their interests is achieved by analysis of sentence structure and the use of Relationship WordNet, a lexical resource that we developed. For analyzing polarities of stakeholder descriptions, we propose an opinion mining method based on the lexical resource Senti WordNet. We also describe an application system we developed for news comparison based on the mining mechanism. This paper presents a user study to validate the proposed methods.

From the viewpoint that most news items report on entities (person, organization and location), we propose a novel stakeholder model to represent and analyze news contents to explore special items in which there is inconsistency in the descriptions. By using this model, we can discover differences in multimedia news items from the perspectives of media types (text, video and audio) and description types (objective, subjective and relationship descriptions). We propose a method of extracting stakeholders as main participants (people, organization, etc.) of the described news event and detect inconsistency to explore the special items by comparing visual and textual descriptions on the exposure level of each stakeholder. A prototype system is implemented and we also show some experimental results to validate the proposed methods.

For understanding human activity, a useful approach is to rank people according to the strength of their relations to a specified person. Similarly, rankings of objects based on such a relation are used in several fields. Several methods have been proposed for computing the strength of a relation between two objects. These methods do not present a reason why an object has a stronger relation to a specified object than another object has. Therefore, it is difficult for a user to understand a ranking obtained using these methods. On the other hand, the authors recently proposed a method for computing the strength of a relation through mining objects to elucidate the relation. We propose a ranking tool based on this method to afford a better understanding of a ranking. Our ranking tool has the following three characteristics for understanding a ranking: (1) it visualizes a relation by displaying objects that are important for elucidating the relation; (2) it classifies ranked objects into several groups, e.g., the two groups of "petroleum exporting countries'' and "petroleum consuming countries'' for ranking countries based on their respective relations to petroleum; and (3) it visualizes a reason explaining why an object has a stronger relation to a specified object than another object has. We explain novel ideas used in our ranking tool for understanding a ranking based on relations, and claim how effective the features of our tool are by presenting examples.

Distribution data naturally arise in countless domains, such as meteorology, biology, geology, industry and economics. However, relatively little attention has been paid to data mining for large distribution sets. Given n distributions of multiple categories and a query distribution Q, we want to find similar clouds (i.e., distributions), to discover patterns, rules and outlier clouds. For example, consider the numerical case of sales of items, where, for each item sold, we record the unit price and quantity; then, each customer is represented as a distribution of 2d points (one for each item he/she bought). We want to find similar users, e.g., for market segmentation, anomaly/fraud detection. We propose to address this problem and present D-search, which includes fast and effective algorithms for similarity search in large distribution datasets. Our main contributions are (1) approximate KL divergence, which can speed up cloud-similarity computations, (2) multi-step sequential scan, which efficiently prunes a significant number of search candidates and leads to a direct reduction in the search cost. We also introduce an extended version of D-search: (3) time-series distribution mining, which finds similar subsequences in time-series distribution datasets. Extensive experiments on real multi-dimensional datasets show that our solution achieves up to 2,300 faster wall-clock time over the naive implementation while it does not sacrifice accuracy.

In order to create more attractive tagclouds that get people interested in tagged content, we propose a simple but novel tagcloud where font size is determined by tag's entropy value, not the popularity to its content. Our method raises users' emotional interest in the content by emphasizing more emotional tags. Our initial experiments show that emotional tagclouds attract more attention than normal tagclouds at first look; thus they will enhance the role of tagcloud as a social signaller.

Protection of user privacy is an important issue of Web applications. Data encryption presents a possible resolution for improving the security level of Web applications. In this paper, we propose a novel mechanism using broadcast encryption and account assignment methods to reduce the decryption cost of Web applications. A notable feature of our mechanism is that the additional function of the application server is not necessary. Moreover, it is easy to apply this method to existing servers to improve their security level. We also show some experimental results to demonstrate the feasibility of our methods.

Time-series data naturally arise in countless domains, such as meteorology, astrophysics, geology, multimedia, and economics. Similarity search is very popular, and DTW (Dynamic Time Warping) is one of the two prevailing distance measures. Although DTW incurs a heavy computation cost, it provides scaling along the time axis. In this paper, we propose FTW (Fast search method for dynamic Time Warping), which guarantees no false dismissals in similarity query processing. FTW efficiently prunes a significant number of the search cost. Experiments on real and synthetic sequence data sets reveals that FTW is significantly faster than the best existing method, up to 222 times.

Web search engines help users find useful information on the World Wide Web (WWW). However, when the same query is submitted by different users, typical search engines return the same result regardless of who submitted the query. Generally, each user has different information needs for his/her query. Therefore, the search result should be adapted to users with different information needs. In this paper, we first propose several approaches to adapting search results according to each user's need for relevant information without any user effort, and then verify the effectiveness of our proposed approaches. Experimental results show that search systems that adapt to each user's preferences can be achieved by constructing user profiles based on modified collaborative filtering with detailed analysis of user's browsing history in one day.

Update management of XML documents is an increasingly important research issue in XML databases, because contents of XML documents evolve as time goes by. Even though, XML databases should be able to effectively process XML queries as well as updates on the documents. We propose a robust node-numbering scheme for XML documents named QRS (quartering-regions scheme). In QRS, reefs (regions expressed by floating-point numbers), a variant of regions, are used for expressing node-numbers. Reefs are almost compatible to regions, and thus they can be used for detecting ancestor-descendant relationship among nodes for the purpose of efficient query processing. Moreover, reefs can cope with updates by utilizing gaps between reefs in terms of floating-point numbers. Consequently, we can avoid node renumbering as much as possible.

This paper presents an approach to bilingual lexicon extraction from comparable corpora and evaluations on Cross-Language Information Retrieval. We explore a bi-directional extraction of bilingual terminology primarily from comparable corpora. A combined statistics-based and linguistics-based model to select best translation candidates to phrasal translation is proposed. Evaluations using a large test collection for Japanese-English revealed the proposed combination of bi-directional comparable corpora, bilingual dictionaries and transliteration, augmented with linguistics-based pruning to be highly effective in Cross-Language Information Retrieval.

In this paper, we propose a retrieval method for multimedia documents. In our method, features of each medium such as text, image, and their layout information are extracted from documents. For a given query, similarity values are calculated for each media, then those values are integrated into one similarity value per document. We propose four methods for calculating the integrated similarity values. Also, we performed experiments using PDF files, and verified the effectiveness of our method.

For most of the index structures for XML data proposed so far, updating is a problem, because an XML element's coordinates are expressed using absolute values. Due to the structural relationship among the elements in XML documents, we have to re-compute these absolute values if the content of the source data is updated. The reconstruction requires the updating of a large portion of the index files, which causes a serious problem, especially when the XML data content is updated frequently. In this paper, we propose an indexing structure scheme based on the relative region coordinates that can effectively deal with the update problem. The main idea is that we express the coordinates of an XML element based on the region of its parent element. We present an algorithm to construct a tree-structured index in which related coordinates are stored together. In consequence, our indexing scheme requires the updating of only a small portion of the index file.

Article Free Access Share on On the equivalence of database restructurings involving object identifiers (extended abstract) Authors: Richard Hull Computer Science Department, University of Southern California, Los Angeles, CA Computer Science Department, University of Southern California, Los Angeles, CAView Profile , Masatoshi Yoshikawa Department of Information and Communication Sciences, Kyoto Sangyo University, Kamigamo, Kita-ku, Kyoto 603, Japan Department of Information and Communication Sciences, Kyoto Sangyo University, Kamigamo, Kita-ku, Kyoto 603, JapanView Profile Authors Info & Claims PODS '91: Proceedings of the tenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systemsApril 1991 Pages 328–340https://doi.org/10.1145/113413.113443Published:01 April 1991Publication History 17citation258DownloadsMetricsTotal Citations17Total Downloads258Last 12 Months14Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A description is given of the concept and implementation techniques of schema virtualization in object-oriented databases. The objective of schema virtualization is to provide users with multiple views of a database. First, the notions of virtual classes and virtual schemata, which are natural extension of views in relational databases, is introduced. Then, procedures to convert a schema into a virtual one, as well as rules schemata and their conversion should satisfy, are discussed. The key issue of the design of virtual classes and virtual schemata is 'regarding procedures as objects'. Closure properties of classes and schemata are also discussed. Finally, several implementation techniques for realizing schema virtualization in Smalltalk-80 are presented.>

Since join operations are expensive, usually join scheduling is very important for query processing. In this paper we will discuss new procedures to handle cyclic queries utilizing dependencies and horizontal decompositions. There are three known procedures for cyclic query processing: (1) Relation merging, (2) Tuple-wise processing, (3) Attribute addition. As join operations are applied to relations which are processed by selection operations, the number of tuples is usually less than the original relation and thus there are situations in which temporary FDs are satisfied. Such FDs can be used to simplify the given query. To convert a given cyclic query into a tree, some relations must satisfy a set of FDs. This can be attained by horizontal decomposition. Tuple-wise processing and attribute addition are shown to be special cases of the FD-based procedure. We have also developed MVD-based procedures which are generalized from the FD-based procedure.

In distributed database systems, the cost to process a query is mainly determined by the amount of communication. Semi-join is a very useful tool to reduce the cost of joins in such systems. There are, however, queries called cyclic ones which cannot be processed by semi-joins only. In this paper the concept of generalized semi-joins is introduced to solve such a problem. To handle an arbitrary cyclic query, first a spanning tree is selected in the corresponding query graph and then generalized semi-joins are applied in the order determined by the tree. Processing of cyclic queries, however, requires more communication cost than processing of tree queries, since in the former case we need to transmit attribute values which are not required in the latter case. A procedure to reduce the communication cost of such additional data is developed, which will make the generalized semi-join based procedures practical.