Schema.org has experienced high growth in recent years. Structured descriptions of products embedded in HTML pages are now not uncommon, especially on e-commerce websites. The Web Data Commons (WDC) project has extracted schema.org data at scale from webpages in the Common Crawl and made it available as an RDF `knowledge graph' at scale. The portion of this data that specifically describes products offers a golden opportunity for researchers and small companies to leverage it for analytics and downstream applications. Yet, because of the broad and expansive scope of this data, it is not evident whether the data is usable in its raw form. In this paper, we do a detailed empirical study on the product-specific schema.org data made available by WDC. Rather than simple analysis, the goal of our study is to devise an empirically grounded set of best practices for using and consuming WDC product-specific schema.org data. Our studies reveal five best practices, each of which is justified by experimental data and analysis.

Given a domain-specific set of concepts, local taxonomy construction (LTC) is the problem of `locally' inducing the neighborhood of a concept (from the set of target concepts) without being given any example links. The problem, despite having practical importance, has received little research attention due to its difficulty (in contrast with link prediction, a problem that resembles it and has undergone broad study). In this paper, we present a formalism and deep empirical study on the LTC problem. In particular, we show that an innovative application of representation learning approaches from the natural language community could be adapted to tackle the problem, often quite effectively. We also present a detailed information retrieval (IR)-based methodology for evaluating these solutions on three real- world product datasets of varying sizes. To the best of our knowledge, this is the first paper to introduce the LTC problem, especially for e-commerce applications, and offer effective, nearly unsupervised, solutions, for addressing it on real-world data.

System deployments of IoT systems have drawn research attention, because it is very challenging to meet both physical and cyber constraints in real systems. In this article, we consider the problem of deploying wireless camera networks inside a complex indoor setting for surveillance applications. We formulate the problem of the minimum connected guarding network whose objective is to place a minimum number of cameras satisfying both visual coverage of the domain and wireless network connectivity. We prove that finding the minimum connected guarding network is NP-hard in both the geometric and discrete settings. We also give a 2-approximation algorithm to the geometric minimum guarding network problem. Motivated by the connection of this problem with the watchman tour problem and the art gallery problem, we developed two algorithms to calculate the locations of camera deployment. By deploying a prototype testbed, we verify the feasibility of the system design. Using simulations on 20 real floor plans, we demonstrate that our solutions reduce the number of cameras by up to 28%, and reduce the number of relay nodes by up to 47%.

The maturing of mobile devices and systems provides an unprecedented opportunity to collect a large amount of real world human motion data at all scales. While the rich knowledge contained in these data sets is valuable in many fields, various types of personally sensitive information can be easily learned from such trajectory data. The ones that are of most concerns are frequent locations, frequent co-locations and trajectory re-identification through spatio-temporal data points. In this work we analyze privacy protection and data utility when trajectory IDs are randomly mixed during co-location events for data collection or publication. We demonstrate through both analyses and simulations that the global geometric shape of each individual trajectory is sufficiently altered such that re-identification via frequent locations, co-location pairs or spatial temporal data points is not possible with high probability. Meanwhile, a decent number of local geometric features of the trajectory data set are still preserved, including the density distribution and local traffic flow.

Robot Coverage Path planning (i.e., the process of providing full coverage of a given domain by one or multiple robots) is a classical problem in the field of robotics and motion planning. The goal of such planning is to provide nearly full coverage while also minimize duplicately visited area. In this paper, we focus on the scenario of path planning on general surface, including planar domains with complex topology, complex terrain, and general surface in 3D space. Our approach described in this paper adopts a natural, intrinsic and global parametrization of the surface for robot path planning, namely the holomorphic quadratic differentials. We give each point on the surface a uv-coordinates naturally represented by a complex number, except for a small number of zero points (singularities). We show that natural, efficient robot paths can be obtained by using such coordinate systems. The method is based on intrinsic geometry and thus can be adapted to general surface exploration in 3D.

In this work, we study privacy preserving trajectory sensing and query when n mobile entities (e.g., mobile devices or vehicles) move in an environment of m checkpoints (e.g, WiFi or cellular towers). The checkpoints detect the appearances of mobile entities in the proximity, meanwhile, employ the MinHash signatures to record the set of mobile entities passing by. We build on the checkpoints a distributed data structure named the MinHash hierarchy, with which one can efficiently answer queries regarding popular paths and other traffic patterns. The MinHash hierarchy has a total of near linear storage, linear construction cost, and logarithmic update cost. The cost of a popular path query is logarithmic in the number of checkpoints. Further, the MinHash signature provides privacy protection using a model inspired by the differential privacy model. We evaluated our algorithm using a large mobility data set and compared with previous works to demonstrate its utilities and performances.

We consider the problem of capacitated kinetic clustering in which n mobile terminals and k base stations with respective operating capacities are given. The task is to assign the mobile terminals to the base stations such that the total squared distance from each terminal to its assigned base station is minimized and the capacity constraints are satisfied. This paper focuses on the development of distributed and computationally efficient algorithms that adapt to the motion of both terminals and base stations. Suggested by the optimal transportation theory, we exploit the structural property of the optimal solution, which can be represented by a power diagram on the base stations such that the total usage of nodes within each power cell equals the capacity of the corresponding base station. We show by using the kinetic data structure framework the first analytical upper bound on the number of changes in the optimal solution, i.e., its stability. On the algorithm side, using the power diagram formulation we show that the solution can be represented in size proportional to the number of base stations and can be solved by an iterative, local algorithm. In particular, this algorithm can naturally exploit the continuity of motion and has orders of magnitude faster than existing solutions using min-cost matching and linear programming, and thus is able to handle large scale data under mobility.

With the recent development of localization and tracking systems for both indoor and outdoor settings, we consider the problem of analyzing and representing the huge amount of natural trajectories from human movements that we expect to gather in the near future. In this paper we argue the topological representation, which records how a target moves around the natural obstacles in the underlying environment, can be sufficiently descriptive for many applications and efficient enough for both storing, comparing and classifying these natural human trajectories. Technically, the representation uses the homotopy type of the trajectory. By using harmonic one-forms and Hodge decomposition, we pre-process the sensor network with a purely decentralized algorithm such that the homology class of a trajectory can be obtained by a simple integration along the trajectory. This supports real-time classification of trajectories up to the homology accuracy with minimum communication cost. We test the effectiveness of our approach by showing how to classify randomly generated trajectories in a multi-level arts museum layout as well as how to distinguish real world taxi trajectories in a large city.

Analysis of Internet topologies has shown that the Internet topology has negative curvature, measured by Gromov's “thin triangle condition”, which is tightly related to core congestion and route reliability. In this work we analyze the discrete Ricci curvature of the Internet, defined by Ollivier [1], Lin et al. [2], etc. Ricci curvature measures whether local distances diverge or converge. It is a more local measure which allows us to understand the distribution of curvatures in the network. We show by various Internet data sets that the distribution of Ricci cuvature is spread out, suggesting the network topology to be non-homogenous. We also show that the Ricci curvature has interesting connections to both local measures such as node degree and clustering coefficient, global measures such as betweenness centrality and network connectivity, as well as auxilary attributes such as geographical distances. These observations add to the richness of geometric structures in complex network theory.

We consider the problem of deployment of cameras inside a complex indoor setting for surveillance applications. We formulate the problem of the minimum guarding network that places a minimum number of cameras satisfying both visual coverage of the domain and wireless network connectivity. We prove that finding the minimum guarding network in both the geometric setting and discrete setting is NP-hard. We also give a 2-approximation algorithm to the geometric minimum guarding network. Motivated by the connection of this problem with the watchman tour problem and the art gallery problem, we develop two algorithms that generate satisfactory results in a prototype testbed and in our simulations.

Homotopic routing asks for a path going around holes according to a given “threading”. Paths of different homo-topy types can be used to improve load balancing and routing resilience. We propose the first lightweight homotopic routing scheme that generates constant bounded stretch compared to the shortest path of the same homotopy type. Our main insight is that in a sequence of triangles to traverse, a message always routed to the nearest point on the next triangle in the sequence travels at most a constant times the length of any shortest path going through the same sequence of triangles. Our routing scheme operates on two levels enabled by a coarse triangulation. The top level is used to specify and represent the requested homotopy type, while the bottom level executes the local greedy routing on a triangle sequence. After a preprocessing step that triangulates the given region and creates a minimum-size auxiliary structure, routing operates greedily at two different resolutions. We also present simulation analysis in a variety of settings and show that the paths indeed have small stretch in practice, considerably shorter than the bounds guaranteed by the theory.

Load balanced routing in a network, i.e., minimizing the maximum traffic load any node carries for unsplittable flows, is a well known NP-hard problem. Finding practical algorithms remains a long standing challenge. In this paper we propose greedy routing using virtual coordinates that achieves both small path stretch ratio (compared to shortest path) and small load balancing ratio (compared to optimal load balanced routing), in a large scale wireless sensor network deployed densely inside a geometric domain with complex shape. We first provide a greedy routing scheme on a disk with a stretch ratio of at most 2, and under which the maximum load is a factor 4√2 smaller than the maximum load under shortest path routing. This is the first simple routing scheme with a small stretch that has been proven to outperform shortest path routing in terms of load balancing. Then we transform a network of arbitrary shape to a disk by an area preserving map φ. We show that both the path length and the maximum traffic load in the original network only increases by an additional factor of d2, where d is the maximum length stretch of φ. Combined with the result on a disk we again achieve both bounded stretch and bounded load balancing ratio. Our simulation results evaluated the practical performance on both quality measures.

First responder applications often require safety surveillance using wireless camera networks~\cite{breadcrums}. To ensure visual sensing coverage, it is crucial to place optical sensor nodes at proper locations. Under the scenario of energy constrained wireless camera deployment, the issue of communication cost should also be considered. Previous camera deployment research (e.g Art Gallery Problem) mainly concerned sensing coverage. One well-known solution for the art gallery problem is to triangulate the objective polygon and then select vertices to ensure full coverage. However, deploying cameras only in the vertices of polygon may induce inefficiency both in number of necessary cameras and overall communication cost. To reduce the cost, we propose two deployment algorithms: 1) connected visibility region planning algorithm for static deployment given the floor plan is known, and 2) connected visibility region tracking algorithm for the dynamic deployment during the run time. In extensive simulations with real floor plans, our algorithms outperform previous solutions significantly.

Along with the growth of cloud computing and mobile devices, the importance of client device identity concern over cloud environment is emerging. To provide a lightweight yet reliable method for device identification, an application layer approach based on clock skew fingerprint is proposed. The developed experimental platform adapts AJAX technology to collect the timestamps of client devices in the cloud server during connection time, then calculate the clock skews of client devices. Few methods based on linear regression and piecewise minimum algorithm are developed to optimize the precision and shorten timestamp collection process. A jump point detection scheme is also proposed to resolve the offset drifting problem, which is usually caused by switching network or temporary disconnection. Finally, two experiments are conducted to study the effectiveness of clock skew fingerprint, and the results illustrate that the false positive rate and the false negative rate, in the worst case, are both no more than 8% when the tolerance threshold is set appropriately.

Broadcast presents a special challenge for wireless sensor networks (WSNs). In some situation such as time synchronization or building routing path, broadcasting messages must be securely transmitted to all nodes, but this process is subject to attack by adversaries. For example, an adversary may try to waste the battery power of intermediate nodes by forcing a compromised node to repeatedly rebroadcast, thus causing a denial-of-service (DoS) attack. One way to solve this problem is use only part of the nodes in the network as the intermediate nodes, limiting the effects of the attack. In this paper, we propose a novel broadcast protocol: broadcast power preserving (BOPP). In BOPP, a packet reception reliability metric of each network component is discovered. This reliability score gives the packet reception rate of each communication edge in the network. With the scoring metric, BOPP can judge the network reliability from time to time and adapt the network to provide maximum reliability while minimizing the energy cost. This enables the network to resist DoS attacks.