Jeffrey Hightower
`Bernt Schiele
`
`Thomas Strang (Eds.)
`
`
`
`LNCS4718
`
`Location-and
`
`Context-Awareness
`
`Third International Symposium, LoCA 2007
`Oberpfaffenhofen, Germany, September 2007
`Proceedings
`
` Q Springer
`
`APPLE EXHIBIT 1015
`Page 1 of 27
`
`

`

`Lecture Notes in Computer Science
`Commenced Publication in 1973
`Founding and Former Series Editors:
`Gerhard Goos, Juris Hartmanis, and Jan van Leeuwen
`
`4718
`
`Editorial Board
`
`David Hutchison
`Lancaster University, UK
`Takeo Kanade
`Carnegie Mellon University, Pittsburgh, PA, USA
`Josef Kittler
`University of Surrey, Guildford, UK
`Jon M. Kleinberg
`Cornell University, Ithaca, NY, USA
`Friedemann Mattern
`ETH Zurich, Switzerland
`John C. Mitchell
`Stanford University, CA, USA
`Moni Naor
`Weizmann Institute of Science, Rehovot, Israel
`Oscar Nierstrasz
`University of Bern, Switzerland
`C. Pandu Rangan
`Indian Institute of Technology, Madras, India
`Bernhard Steffen
`University of Dortmund, Germany
`Madhu Sudan
`Massachusetts Institute of Technology, MA, USA
`Demetri Terzopoulos
`University of California, Los Angeles, CA, USA
`Doug Tygar
`University of California, Berkeley, CA, USA
`Moshe Y. Vardi
`Rice University, Houston, TX, USA
`Gerhard Weikum
`Max-Planck Institute of Computer Science, Saarbruecken, Germany
`
`APPLE EXHIBIT 1015
`Page 2 of 27
`
`

`

`Jeffrey Hightower Bernt Schiele
`Thomas Strang (Eds.)
`
`Location- and
`Context-Awareness
`
`Third International Symposium, LoCA 2007
`Oberpfaffenhofen, Germany, September 20-21, 2007
`Proceedings
`
`1 3
`
`APPLE EXHIBIT 1015
`Page 3 of 27
`
`

`

`Volume Editors
`
`Jeffrey Hightower
`Intel Research Seattle
`1100 NE 45th St., Seattle, WA 98105, USA
`E-mail: jeffrey.r.hightower@intel.com
`
`Bernt Schiele
`TU Darmstadt
`Computer Science Department
`Hochschulstrasse 10, 64289 Darmstadt, Germany
`E-mail: schiele@informatik.tu-darmstadt.de
`
`Thomas Strang
`German Aerospace Center
`Institute of Communications and Navigation
`82234 Wessling/Oberpfaffenhofen, Germany
`E-mail: Thomas.Strang@dlr.de
`and
`Digital Enterprise Research Institute (DERI)
`University of Innsbruck, 6020 Innsbruck, Austria
`
`Library of Congress Control Number: 2007934918
`
`CR Subject Classification (1998): H.3, H.4, C.2, H.5, K.8
`
`LNCS Sublibrary: SL 3 – Information Systems and Application, incl. Internet/Web
`and HCI
`
`ISSN
`ISBN-10
`ISBN-13
`
`0302-9743
`3-540-75159-9 Springer Berlin Heidelberg New York
`978-3-540-75159-5 Springer Berlin Heidelberg New York
`
`This work is subject to copyright. All rights are reserved, whether the whole or part of the material is
`concerned, specifically the rights of translation, reprinting, re-use of illustrations, recitation, broadcasting,
`reproduction on microfilms or in any other way, and storage in data banks. Duplication of this publication
`or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965,
`in its current version, and permission for use must always be obtained from Springer. Violations are liable
`to prosecution under the German Copyright Law.
`
`Springer is a part of Springer Science+Business Media
`
`springer.com
`
`© Springer-Verlag Berlin Heidelberg 2007
`Printed in Germany
`
`Typesetting: Camera-ready by author, data conversion by Scientific Publishing Services, Chennai, India
`Printed on acid-free paper
`SPIN: 12162987
`06/3180
`5 4 3 2 1 0
`
`APPLE EXHIBIT 1015
`Page 4 of 27
`
`

`

`Preface
`
`These proceedings contain the papers presented at the 3rd International Sym-
`posium on Location- and Context-Awareness in September of 2007.
`Computing has become mobile, wireless, and portable. The range of contexts
`encountered while sitting at a desk working on a computer is very limited com-
`pared to the large variety of situations experienced away from the desktop. For
`computing to be relevant and useful in these emerging situations, computers will
`need to take advantage of users location, activities, goals, abilities, preferences,
`interruptibility, affordances, and surroundings. With this contextual awareness,
`we can expect computers to deliver information, services, and entertainment in
`a way that maximizes convenience and minimizes intrusion.
`This symposium presented research aimed at sensing, inferring, and using
`location and context data in ways that help the user. Developing awareness in-
`volves research in sensing, inference, data representation, and design. We sought
`technical papers describing original, previously unpublished research results in-
`cluding:
`
`– Sensing location and context
`– Inference techniques for context from low-level sensor data
`– Privacy and sharing of location and context information
`– User studies of location- and context-aware systems
`
`Our call for papers resulted in 55 submissions, each of which was assigned to
`members of our Program Committee. After reviews and e-mail discussions, we
`selected 17 papers for publication in these proceedings.
`We extend a sincere thank you to all the authors who submitted papers, to
`the 33 hard-working members of our Program Committee, and to our external
`reviewers.
`
`September 2007
`
`Jeffrey Hightower
`Bernt Schiele
`Thomas Strang
`
`APPLE EXHIBIT 1015
`Page 5 of 27
`
`

`

`Organization
`
`Program Committee
`
`Gregory Abowd
`Witold Abramowicz
`Alessandro Acquisti
`Michael Beigl
`Carlos Bento
`Gaetano Borriello
`Jim Crowley
`Eyal de Lara
`Anind Dey
`Alois Ferscha
`Hans Gellersen
`Robert Harle
`Mike Hazas
`Jaga Indulska
`Minkyong Kim
`John Krumm
`Reto Krummenacher
`Anthony LaMarca
`Marc Langheinrich
`Claudia Linnhoff-Popien
`Paul Lukowicz
`Max M¨uhlh¨auser
`Kurt Partridge
`Shwetak Patel
`Alex Pentland
`Matt Reynolds
`Kay Roemer
`Chris Schmandt
`Albrecht Schmidt
`Tim Sohn
`Hiroyuki Tarumi
`Alex Varshavsky
`Andy Wilson
`
`Georgia Tech
`Poznan University of Economics
`CMU
`TU Braunschweig
`University of Coimbra
`University of Washington
`INRIA, France
`University of Toronto
`CMU
`University of Linz
`Lancaster University
`University of Cambridge
`Lancaster University
`University of Queensland
`IBM Research
`Microsoft Research
`DERI Innsbruck
`Intel Research
`ETH Zurich
`LMU Munich
`University of Passau
`TU Darmstadt
`PARC
`Georgia Tech
`MIT
`ThingMagic Inc.
`ETH Zurich
`MIT
`Fraunhofer IAIS and University of Bonn
`UC San Diego
`Kagawa University
`University of Toronto
`Microsoft Research
`
`External Reviewers
`
`Mohammed Al-Loulah
`Philippe Golle
`
`Lancaster University
`PARC
`
`APPLE EXHIBIT 1015
`Page 6 of 27
`
`

`

`VIII
`
`Organization
`
`Sponsoring Institutions
`
`German Aerospace Center (DLR)
`Intel
`
`APPLE EXHIBIT 1015
`Page 7 of 27
`
`

`

`Table of Contents
`
`WiFi Location Technology
`
`Bootstrapping a Location Service Through Geocoded Postal
`Addresses . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Gayathri Chandrasekaran, Mesut Ali Ergin, Marco Gruteser, and
`Richard P. Martin
`
`Deployment, Calibration, and Measurement Factors for Position Errors
`in 802.11-Based Indoor Positioning Systems . . . . . . . . . . . . . . . . . . . . . . . . .
`Thomas King, Thomas Haenselmann, and Wolfgang Effelsberg
`
`LifeTag: WiFi-Based Continuous Location Logging for Life Pattern
`Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Jun Rekimoto, Takashi Miyaki, and Takaaki Ishizawa
`
`Activity and Situational Awareness
`
`Scalable Recognition of Daily Activities with Wearable Sensors . . . . . . . .
`Tˆam Hu`ynh, Ulf Blanke, and Bernt Schiele
`
`Information Overlay for Camera Phones in Indoor Environments . . . . . . .
`Harlan Hile and Gaetano Borriello
`
`SocialMotion: Measuring the Hidden Social Life of a Building . . . . . . . . . .
`Christopher R. Wren, Yuri A. Ivanov, Ishwinder Kaur,
`Darren Leigh, and Jonathan Westhues
`
`Taxonomy, Architectures, and a Broader Perspective
`
`A Unified Semantics Space Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Juan Ye, Lorcan Coyle, Simon Dobson, and Paddy Nixon
`
`Federation and Sharing in the Context Marketplace . . . . . . . . . . . . . . . . . .
`Carsten Pils, Ioanna Roussaki, Tom Pfeifer,
`Nicolas Liampotis, and Nikos Kalatzis
`
`A Taxonomy for Radio Location Fingerprinting . . . . . . . . . . . . . . . . . . . . . .
`Mikkel Baun Kjærgaard
`
`1
`
`17
`
`35
`
`50
`
`68
`
`85
`
`103
`
`121
`
`139
`
`The Meaning of Place
`
`Inferring the Everyday Task Capabilities of Locations . . . . . . . . . . . . . . . .
`Patricia Shanahan and William G. Griswold
`
`157
`
`APPLE EXHIBIT 1015
`Page 8 of 27
`
`

`

`X
`
`Table of Contents
`
`The Whereabouts Diary . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Gabriella Castelli, Marco Mamei, and Alberto Rosi
`
`Adaptive Learning of Semantic Locations and Routes . . . . . . . . . . . . . . . . .
`Keshu Zhang, Haifeng Li, Kari Torkkola, and Mike Gardner
`
`Radio Issues in Location Technology
`
`Signal Dragging: Effects of Terminal Movement on War-Driving in
`CDMA/WCDMA Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Daehyung Jo, Jeongkeun Lee, Semun Lee, Taejoon Ha,
`Taekyoung Kwon, and Yanghee Choi
`
`Modeling and Optimizing Positional Accuracy Based on Hyperbolic
`Geometry for the Adaptive Radio Interferometric Positioning System . . .
`Hao-ji Wu, Ho-lin Chang, Chuang-wen You, Hao-hua Chu, and
`Polly Huang
`
`New Approaches to Location Estimation
`
`Inferring Position Knowledge from Location Predicates . . . . . . . . . . . . . . .
`J¨org Roth
`
`Preserving Anonymity in Indoor Location System by Context Sensing
`and Camera-Based Tracking . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`Takeshi Iwamoto, Arei Kobayashi, and Satoshi Nishiyama
`
`Localizing Tags Using Mobile Infrastructure . . . . . . . . . . . . . . . . . . . . . . . . .
`Ying Zhang, Kurt Partridge, and Jim Reich
`
`Author Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`
`175
`
`193
`
`211
`
`228
`
`245
`
`263
`
`279
`
`297
`
`APPLE EXHIBIT 1015
`Page 9 of 27
`
`

`

`The Whereabouts Diary
`
`Gabriella Castelli, Marco Mamei, and Alberto Rosi
`
`Dipartimento di Scienze e Metodi dell’Ingegneria – Università di Modena e Reggio Emilia
`Via Amendola 2 – 42100 Reggio Emilia, Italy
`{gabriella.castelli,marco.mamei,alberto.rosi}@unimore.it
`
`Abstract. The user profile is one of the main context-information in a wide
`range of pervasive computing applications. Modern handheld devices provided
`with localization capabilities could automatically create a diary of user’s
`whereabouts and use that information as a surrogate (or a complement) of the
`user profile. The places we go, in fact, reveal also something about us, for
`example, two persons can be matched as compatible given the fact they visit the
`same places. Web-retrieved information, and the temporal patterns with which
`different places are visited, can be used to automatically define meaningful
`semantic labels to the visited places. In our work we used geocoding and white-
`pages Web-services to extract information about a place, and Bayesian
`networks to classify places on the basis of the time in which they have been
`visited. In this paper we describe the general idea at the basis of the
`whereabouts diary, discuss our implementation, and present experimental
`results. Finally, several applications that can exploit the diary are illustrated.
`
`1 Introduction
`
`The recent diffusion of handheld devices and smart phones equipped with localization
`capabilities1 is opening new scenarios in the development of context-aware services.
`The location itself is an extremely useful source of information: location-based services
`and location-based information retrieval allow to get resources that are relevant and
`practically accessible given the actual location of the user [3, 4]. More than that, the
`places we go can reveal also something about us, and can be used as a surrogate or a
`complement to form a better user profile. For example, a matchmaking application
`could infer that two persons are compatible given the fact that they visit almost the same
`places. Moreover, if the places are tagged semantically (e.g., work, home, pub, etc.) the
`application could infer more advanced relationships among the persons. For example,
`two persons visiting the same “work” place could be marked as colleagues, while
`persons visiting the same “home” place could be marked as relatives.
`In this paper we present the ideas and a first prototype implementation of the
`whereabouts diary: an application, running on a GPS-equipped handheld device that
`records the list of relevant places visited by the user. The diary runs autonomously
`without requiring user’s interactions and is able to classify semantically the places
`being visited in an unsupervised way. Relevant places can be extracted by considering
`
`1 The U.S. E911 and European E112 initiatives require localization capability for calls placed
`to emergency services by mobile phones.
`
`J. Hightower, B. Schiele, and T. Strang (Eds.): LoCA 2007, LNCS 4718, pp. 175–192, 2007.
`© Springer-Verlag Berlin Heidelberg 2007
`
`APPLE EXHIBIT 1015
`Page 10 of 27
`
`

`

`176
`
`G. Castelli, M. Mamei, and A. Rosi
`
`clusters and dropouts in the GPS signal (typically indicating the user staying in a
`place or entering in a building). Semantic information can be added by exploiting the
`structure of people daily routine. For example, the place where the user usually
`spends night-time can be tagged semantically as “home”, while the place where the
`user usually goes from 8am to 6pm can be tagged as “work”. Specifically, we realized
`a set of Bayesian networks to diagnose the kind of place given the temporal pattern of
`user visits. Further information can be extracted by geocoding the place and mining
`the Web in search for relevant information. For example, the fact that the user was at
`the coordinates (lon: -80.239, lat: 25.955) on the 02/04/07 evening, can be easily
`geocoded to infer that the user was actually at the Dolphin Stadium in South Florida.
`Moreover, such information could be further refined extracting from the Web the fact
`that the SuperBowl was actually playing that night in that stadium. The result is a
`diary describing the user daily life and that could provide useful profile information to
`other applications.
`The rest of this paper is organized as follows: Section 2 describes the general idea
`and our current implementation of the whereabouts diary. Section 3 presents some
`experiments we conducted to test the effectiveness of our prototype. Section 4
`discusses some applications that could be realized with the diary. Section 5 presents
`some related work. Section 6 concludes and presents future work diary.
`
`2 The Whereabouts Diary
`
`In this section we first present the conceptual idea beneath the whereabouts diary,
`then we detail our current implementation.
`
`2.1 General Idea
`
`The construction of the whereabouts diary is an incremental process. Starting from the
`log of the GPS readings (or of other kind of localization devices), it is possible to run
`segmentation and clustering algorithms to infer the places where the user spends most
`of his time [9]. The result of this first operation is a list of places described in terms of
`longitude and latitude, and a list of time intervals associated to each of the coordinates
`indicating when the user has been there. This first process creates a diary like the one
`presented in Fig. 1.
`
`Longitude
`-73.974
`…
`
`Latitude
`40.763
`…
`
`Time
`July, 4, 2006, 4:35pm-5:41pm
`…
`
`Fig. 1. Diary based on GPS coordinates
`
`A simple list of coordinates is only partially informative and the need of translating
`from positions to places (i.e., adding semantic meaningful tags to the discovered
`coordinates) has been widely recognized [8]. A diary containing information like “the
`
`APPLE EXHIBIT 1015
`Page 11 of 27
`
`

`

`
`
`The Whereabouts Diary
`
`177
`
`user was at home” rather than “the user was at coordinates (10.873, 44.630)” would
`be naturally much more informative and easy to use in context-aware applications.
`A first step in the process of adding semantic information would be to translate
`from coordinates to addresses. This can be done via standard tracking and geocoding
`services (as common GPS navigators do). However, because of errors in GPS
`localization and errors in the process of segmenting and clustering the GPS readings
`to identify relevant places, in most of the situations, it will not be possible to identify
`the unique address where the user is located, and only a partial estimate can be given
`(e.g., all the addresses within 10 meters from a given place are actually taken into
`consideration). This second step converts the diary in the one depicted in Fig. 2.
`
`Place
`123, 5th Ave, NY, USA
`4,5,…,21, 26th St., NY, USA
`…
`
`Time
` July, 4, 2006, 4:35pm-5:41pm
`July 6, 2006, 7:00am – 8:00am
`…
`
`Fig. 2. Diary based on addresses. Because of GPS errors multiple addresses can be associated
`to a single place.
`
`A third step can try to mine the Web to identify what is in a particular address. The
`primary source of information in this context would come from yellow- and white-
`pages services. However, due to the aforementioned localization errors, this process
`will return in some of the cases a list of all the businesses performed in the geocoded
`addresses. Still, in some situations a single exact match could be retrieved like in the
`case of the user being in a big stadium or entering a big shopping mall.
`Even more semantic information could derive by searching relevant events that
`happened in that place at that time. For example, it could be possible to extract from
`the Web the fact that “the 4th of July parade” took place near the geocoded location at
`the same time the user was there. This process could create a diary like the one
`depicted in Fig. 3.
`
`Place
`4th July Parade
`126, 13th St., NY, USA
`Starbucks Coffee || Uno’s Pizza
`….
`
`Time
` July, 4, 2006, 4:35pm-5:41pm
`July 5, 2006, 11:00pm – 7:00am
`July 6, 2006, 7:00am – 8:00am
`…
`
`Fig. 3. Diary based on places. Because of errors in the previous phases, multiple businesses can
`be associated to a single place.
`
`Finally, if the user activities are profiled in some way (e.g., the diary may know a
`priori that the user tends to stay at home at night), then the diary application can give
`labels to places by looking at the temporal patterns in which places are visited. For
`example, the place most visited at night during weekdays can be meaningfully labeled
`as “Home”. Such kind of analysis can be also used in combination with commonsense
`information [13] to disambiguate between alternative retrieved places. For example,
`
`APPLE EXHIBIT 1015
`Page 12 of 27
`
`

`

`178
`
`G. Castelli, M. Mamei, and A. Rosi
`
`in the table in Fig. 3 the ambiguity among “Starbucks Coffee” and “Uno’s Pizza” can
`be resolved (at least from a probabilistic point of view) in favor of the former, in
`consideration of the fact the place has been visited from 7:00 am to 8:00 am.
`Of course, should other kind of sensing devices be available (e.g., RFID and NFC
`– Near Field Communication – readers), classification could use such information to
`better identify the places. For example, a powerful source of data could come from
`credit card transaction records that would identify not only in which shop the user has
`been, but also what he has bought (some recent proposals in the context of mobile
`wallet applications go in this direction [5]). In the end, the combination of all the
`above steps leads to a diary close to the one in Fig. 4.
`
`Place
`4th July Parade
`Home
`Starbucks Coffee
`….
`
`Time
` July, 4, 2006, 4:35pm-5:41pm
`July 5, 2006, 11pm – 7am
`July 5, 2006, 7am – 8am
`…
`
`Fig. 4. Diary based on personalized places
`
`In its final form the diary represents a powerful source of context information
`allowing to extrapolate user’s habits, preferences and routine behavior.
`
`2.2 Implementation
`
`The whereabouts diary can be built incrementally and automatically on the basis of
`the user’s trace of locations. In our current implementation the trace is acquired only
`via a GPS, however other localization mechanisms such as WiFi or Cell tower
`triangulation can be used as well [9].
`The first step is to segment user’s GPS trace to find “relevant” places. Following
`an approach similar to the one proposed in [15, 22], we tagged as relevant those
`places for which either one of the following conditions apply:
`1. The GPS signal is lost for at least T seconds and it is re-acquired later on at a
`distance of less than L meters from where it was lost. This reflects the situation
`in which a user enters a building and leaves it after some time. Some empirical
`evaluations let us to set T = 20 minutes, L = 20 meters. The constraint on time
`is important to wash out GPS signal glitches, the constraint on space is useful to
`avoid those situation in which the GPS has been shut down and the user moves
`away.
`2. The GPS readings over a time window of W seconds are clustered within a
`radius of R meters from each other. This reflects the situation in which the user
`stays for a long time in a place like a park or a square. Some empirical
`evaluations let us to set W = 20 minutes, R = 100 meters.
`
`The list of relevant places is built online and incrementally. When a set of coordinates
`meets one of the above criteria, the system looks in the list of the already discovered
`places for one closer than L = 10 meters to the coordinates. If such a place does not
`
`APPLE EXHIBIT 1015
`Page 13 of 27
`
`

`

`
`
`The Whereabouts Diary
`
`179
`
`exist, a new place is created and the time of visit is recorded. If the place exists, the
`place coordinates are averaged with the new coordinates, and if enough time has
`passed since the previous visit (30 min), the time of the new visit is recorded. The
`output of this algorithm is represented with Google Earth in Fig. 5.
`
`Fig. 5. Path and relevant places depicted in Google Earth
`
`
`
`The coordinates associated to places have been translated into addresses using a
`geocoding service. Most of the geocoding services available online (e.g., that provided
`by the Google Maps API) translate addresses into coordinates. Instead, the diary needs
`the reverse operation: from coordinates to addresses. We developed a “reverse”
`geocoding for our region, on the basis of maps available from a commercial navigator
`software. Once such maps are available, the approach is rather straightforward: the
`coordinates are mapped to the closer map entry (i.e., address) being available.
`To take into account GPS and geocoding inaccuracies, and the errors introduced by
`the place retrieving process, the diary application tries to reverse geocode all the
`addresses within a radius of 10m from the place being segmented. Thus, the diary
`actually creates a list of candidate addresses where the user has been.
`The next step is to translate addresses into businesses (i.e., shops, offices, etc.). The
`ideal result is to have in the diary entries like “Starbuck’s coffee”, rather than “234,
`Marlborough st.”. To perform this operation we screen-scraped information coming
`from a widely used online white-pages service2 in our region allowing to query for
`who is at a given address. This operation is trivially achieved using the tools provided
`by the htmlparser3 software. In particular, each geocoded address belonging to a given
`place (as provided by the previous step) is looked up in the white-pages and the
`
`2 www.paginebianche.it
`3 htmlparser.sourceforge.net
`
`APPLE EXHIBIT 1015
`Page 14 of 27
`
`

`

`180
`
`G. Castelli, M. Mamei, and A. Rosi
`
`corresponding business is retrieved. The result of this process is a set of entries
`labeled with the possible businesses found in that place. Fig. 6 shows the result of this
`process for a given place in Google Earth. This translation process in not completely
`accurate, since several addresses are not listed in the white-pages (mainly due to
`privacy constraints). Still, the fact that most public businesses (like shops, etc.) are
`listed, while several private houses are not, allows to prune out a lot of unlikely
`addresses being discovered by the previous step. Private spaces like “home” – that are
`likely not to be listed in the white-pages – can be derived from other kind of analysis
`described below.
`
`Fig. 6. Extracted information related to a given place
`
`
`
`The final step in our implementation is more challenging. The diary tries to
`automatically extract semantic information to describe the relevant places from a
`personal point of view.
`To this end, for each place being identified in the first phase, the diary creates a
`Bayesian network to analyze the temporal pattern in which the place has been visited
`by the user (see Fig. 7).The Bayesian network is composed of 4 nodes.
`
`1. The weekend node represents a boolean variable used to represent whether a
`given observation takes place in the weekend or not. This node is always
`observed on the basis of the information stored in the GPS signal. This
`information represents the variability in people behavior between weekdays and
`weekends.
`2. The hour node is a 24-values discrete node storing the time of day. This node is
`always observed on the basis of the information stored in the GPS signal.
`3. The kind of place node is a discrete node modeling what a given place is. In our
`implementation, we try to classify among 5 different kind of places: home,
`
`APPLE EXHIBIT 1015
`Page 15 of 27
`
`

`

`
`
`The Whereabouts Diary
`
`181
`
`work, restaurant (to indicate any kind of dining place), pub (to indicate any kind
`of evening entertainment), and disco (to indicate any kind of late-night
`entertainment). This classification is rather arbitrary, and each user of the diary
`should provide the kinds of place that best match his habits. This node is never
`observed, and is inferred by probability computations.
`4. The happens node is a boolean variable expressing whether the user visits that
`place at that time. This node is always observed on the basis of the outcomes of
`the diary localization phase.
`
`The role of the Bayesian network is to encode the routine of the user daily life. This is
`done by compiling the probability distribution associated to the fact that the user, in a
`given moment, is in a certain kind of place. For example, the probability of the user
`being at home during weekdays is depicted in the table in Fig. 8.
`
`Fig. 7. Bayesian network to classify places. White nodes are those that will be provided as
`evidence.
`
`
`
`Weekend = false, Kind of Place = home
`
`Time
`
`P(happens)
`= true
`
`11pm-
`6am
`0.8
`
`7am 8am 9am-
`1pm
`0.2
`
`0.6
`
`0.4
`
`2pm-
`5pm
`0.2
`
`6pm-
`7pm
`0.4
`
`8pm 9pm 10pm
`
`0.5
`
`0.6
`
`0.7
`
`Fig. 8. Conditional probability table describing the probability of the user being at home during
`weekdays
`
`Similar tables can be created for other kind of places. In our current implementat-
`ion, these tables are compiled by hand by the users that are asked to self-report the
`likelihood of being in a given kind of place at a given time. Such kind of data could
`be derived automatically also by a labeled trace of user’s past whereabouts, using
`standard learning algorithms [18]. Once the tables are filled in, basic inference
`operations in Bayesian networks will be used to derive the most likely kind of place
`given the visit pattern.
`
`APPLE EXHIBIT 1015
`Page 16 of 27
`
`

`

`182
`
`G. Castelli, M. Mamei, and A. Rosi
`
`Specifically, when the diary previous phases identify that the user is visiting a
`place, the corresponding Bayesian network is retrieved, and the weekend, hour,
`happens nodes are set to their actual values (the happens node is trivially set to true to
`indicate that there is a visit). Then, the diary computes the probability distribution of
`the kind of place node. The newly computed distribution will be used as a prior for
`subsequent visits. This naturally allows evidences to add up, actually enabling the
`Bayesian network to classify the places on the basis of the visit temporal pattern. The
`results of the Bayesian classifier for two places in our dataset is reported in Fig. 9.
`
`Fig. 9. Outputs of the Bayesian network classifier for two places
`
`
`
`
`
`3 Experiments
`
`To test the effectiveness of the whereabouts diary, we collected GPS traces for three
`weeks from three members of our research team (the authors) as they went about their
`normal lives. Each member carried either an i-mate PDA 2K smart phone, or a HP
`IPAQ RX3700 pda, connected with a Bluetooth GPS reader. GPS signal has been
`acquired at 0.1Hz and processed on the fly by the handheld device. Overall, we
`acquired about 90000 GPS poses amounting at 360 MB of data. Overall, this resulted
`in 25 places being identified as relevant.
`In particular, the diary is a J2ME – personal profile application that:
`
`1. Collects and stores the GPS trace log.
`2. Runs the clustering algorithm to identify relevant places.
`3. Creates a queue of the places to be resolved by the on-line (reverse) geocoding
`and white-pages services. Places are actually resolved whenever a WiFi
`connection becomes available.
`4. Dynamically creates a Bayesian network for each newly discovered place.
`5. When a relevant place is visited, the associated Bayesian network is retrieved, and
`the probability distribution to describe the kind of place is updated accordingly to
`the time of visit. Bayesian operations are implemented on the basis of the
`software described in [14].
`
`During the data collection weeks, data collectors recorded ground-truth information
`about the places they have been. Such information has been collected with a simple
`notepad application running on the PDAs and allowing to write a textual description
`of where the user has been at a given time.
`
`APPLE EXHIBIT 1015
`Page 17 of 27
`
`

`

`
`
`The Whereabouts Diary
`
`183
`
`All the data have been recorded in our region in Italy (none of the data collectors
`have been abroad during that time). The region is characterized by rather small and
`short buildings. On the one hand, this means that GPS signal problems related to
`urban canyons are less severe, and it is usually easy to get fairly accurate GPS
`positioning. On the other hand, buildings are packed closed to each others, and thus
`also small errors can produce wrong address translations.
`In the following, we present some results obtained by comparing the whereabouts
`diary entries, after some weeks of usage, with recorded ground-truth information.
`In a first set of experiments, we tried to verify the accuracy of the algorithm to
`identify relevant places on the basis of the GPS trace log. Following an approach
`similar to [9], we classify the incorrect results into: (i) wrong: the user is in a place,
`but the diary reports he is in a different place, (ii) false negative: the user is in a place,
`but the diary reports he is moving, (iii) false positive: the user is moving, but the diary
`reports he is in a place. The results of this experiment are reported in Fig. 10, and they
`actually show the average of the results obtained by the data collectors. The results we
`obtained show that the algorithm is correct in 84.7% of the cases. This figure is
`coherent with the results presented in [9] with regard to the A-S algorithm [1] that is
`the one closer to our implementation. The high-percentage of false negatives
`(compared to the other cases) is mainly due to the fact sometimes the GPS takes a
`long time before acquiring the signal. Thus, it can happen that a user leaves a
`building, and the trace of the GPS is acquired only when he is already far away. In
`such a situation the place is not detected given the constraint on the maximum
`distance of spatial disconnection described in Sect. 2.2.
`
`Incorrect Results Breakdown
`
`0.2
`0.18
`0.16
`0.14
`0.12
`0.1
`0.08
`0.06
`0.04
`0.02
`0
`
`prob. of error
`
`wrong
`
`false negative
`
`false positive
`
`
`
`Fig. 10. Errors in the algorithm to identify relevant places on the basis of the GPS trace log.
`Place identification is correct in 84.7% of the cases. Errors are divided as reported in the graph.
`
`In a second set of experiments, we tried to verify the results of the (reverse)
`geocoding service. Basically, the idea is to verify the impact of localization errors in
`the process of geocoding. It is worth noticing that the maps we used to perform this
`operation record only the first and the last number of a street segment and span,
`
`APPLE EXHIBIT 1015
`Page 18 of 27
`
`

`

`184
`
`G. Castelli, M. Mamei, and A. Rosi
`
`uniformly, all the other numbers among the segment. This of course introduces
`further errors in that it does not take in to account the differences in the sizes of the
`buildings.
`Since the pl