=Paper= {{Paper |id=Vol-1313/paper_06 |storemode=property |title=Big Data und der Fluch der Dimensionalität: Die effiziente Suche nach Quasi-Identifikatoren in hochdimensionalen Daten |pdfUrl=https://ceur-ws.org/Vol-1313/paper_6.pdf |volume=Vol-1313 |dblpUrl=https://dblp.org/rec/conf/gvd/GrunertH14 }} ==Big Data und der Fluch der Dimensionalität: Die effiziente Suche nach Quasi-Identifikatoren in hochdimensionalen Daten== https://ceur-ws.org/Vol-1313/paper_6.pdf

Big Data und der Fluch der Dimensionalität
Die effiziente Suche nach Quasi-Identifikatoren in hochdimensionalen Daten
Hannes Grunert Andreas Heuer
Lehrstuhl für Datenbank- und Lehrstuhl für Datenbank- und
Informationssysteme Informationssysteme
Universität Rostock Universität Rostock
Albert-Einstein-Straße 22 Albert-Einstein-Straße 22
hg(at)informatik.uni-rostock.de ah(at)informatik.uni-rostock.de

Kurzfassung gen Handlungen des Benutzers abgeleitet, sodass die smarte
In smarten Umgebungen werden häufig große Datenmengen Umgebung eigenständig auf die Bedürfnisse des Nutzers rea-
durch eine Vielzahl von Sensoren erzeugt. In vielen Fällen gieren kann.
werden dabei mehr Informationen generiert und verarbei- In Assistenzsystemen [17] werden häufig wesentlich mehr
tet als in Wirklichkeit vom Assistenzsystem benötigt wird. Informationen gesammelt als benötigt. Außerdem hat der
Dadurch lässt sich mehr über den Nutzer erfahren und sein Nutzer meist keinen oder nur einen sehr geringen Einfluss
Recht auf informationelle Selbstbestimmung ist verletzt. auf die Speicherung und Verarbeitung seiner personenbe-
Bestehende Methoden zur Sicherstellung der Privatheits- zogenen Daten. Dadurch ist sein Recht auf informationel-
ansprüche von Nutzern basieren auf dem Konzept sogenann- le Selbstbestimmung verletzt. Durch eine Erweiterung des
ter Quasi-Identifikatoren. Wie solche Quasi-Identifikatoren Assistenzsystems um eine Datenschutzkomponente, welche
erkannt werden können, wurde in der bisherigen Forschung die Privatheitsansprüche des Nutzers gegen den Informati-
weitestgehend vernachlässigt. onsbedarf des Systems überprüft, kann diese Problematik
In diesem Artikel stellen wir einen Algorithmus vor, der behoben werden.
identifizierende Attributmengen schnell und vollständig er- Zwei Hauptaspekte des Datenschutzes sind Datenvermei-
kennt. Die Evaluierung des Algorithmus erfolgt am Beispiel dung und Datensparsamkeit. In §3a des Bundesdatenschutz-
einer Datenbank mit personenbezogenen Informationen. gesetzes [1] wird gefordert, dass
[d]ie Erhebung, Verarbeitung und Nutzung
”
ACM Klassifikation personenbezogener Daten und die Auswahl und
K.4.1 [Computer and Society]: Public Policy Issues— Gestaltung von Datenverarbeitungssystemen [...]
Privacy; H.2.4 [Database Management]: Systems—Que- an dem Ziel auszurichten [sind], so wenig perso-
ry Processing nenbezogene Daten wie möglich zu erheben, zu
verarbeiten oder zu nutzen.“.
Stichworte Mittels einer datensparsamen Weitergabe der Sensor- und
Datenbanken, Datenschutz, Big Data Kontext-Informationen an die Analysewerkzeuge des Assis-
tenzsystems wird nicht nur die Datenschutzfreundlichkeit
des Systems verbessert. Bei der Vorverdichtung der Daten
1. EINLEITUNG durch Selektion, Aggregation und Komprimierung am Sen-
Assistenzsysteme sollen den Nutzer bei der Arbeit (Am- sor selbst lässt sich die Effizienz des Systems steigern. Die
bient Assisted Working) und in der Wohnung (Ambient Privatheitsansprüche und der Informationsbedarf der Ana-
Assisted Living) unterstützen. Durch verschiedene Senso- lysewerkzeuge können als Integritätsbedingungen im Daten-
ren werden Informationen über die momentane Situation banksystem umgesetzt werden. Durch die Integritätsbedin-
und die Handlungen des Anwenders gesammelt. Diese Da- gungen lassen sich die notwendigen Algorithmen zur An-
ten werden durch das System gespeichert und mit weiteren onymisierung und Vorverarbeitung direkt auf dem Datenbe-
Daten, beispielsweise mit dem Facebook-Profil des Nutzers stand ausführen. Eine Übertragung in externe Programme
verknüpft. Durch die so gewonnenen Informationen lassen bzw. Module, die sich evtl. auf anderen Recheneinheiten be-
sich Vorlieben, Verhaltensmuster und zukünftige Ereignis- finden, entfällt somit.
se berechnen. Daraus werden die Intentionen und zukünfti- Für die Umsetzung von Datenschutzbestimmungen
in smarten Umgebungen wird derzeit das PArADISE1 -
Framework entwickelt, welches insbesondere die Aspekte
der Datensparsamkeit und Datenvermeidung in heteroge-
nen Systemumgebungen realisieren soll.
In [3] stellen wir ein einfaches XML-Schema vor, mit der
Copyright c by the paper’s authors. Copying permitted only sich Privatheitsansprüche durch den Nutzer von smarten
for private and academic purposes. Systemen formulieren lassen. Dabei wird eine Anwendung
In: G. Specht, H. Gamper, F. Klan (eds.): Proceedings of the 26th GI- 1
Workshop on Foundations of Databases (Grundlagen von Datenbanken), Privacy-aware assistive distributed information system
21.10.2014 - 24.10.2014, Bozen, Italy, published at http://ceur-ws.org. environment
innerhalb eines abgeschlossenen Systems in ihre Funktionali- pel (ti ) angibt. Ein Quasi-Identifikator QI := {A1 , ..., An }
täten aufgeteilt. Für jede Funktionalität lässt sich festlegen, ist für eine Relation R entsprechend definiert:
welche Informationen in welchem Detailgrad an das System ≥p
weitergegeben werden dürfen. Dazu lassen sich einzelne At- Quasi-Identifikator. ∀ t1 , t2 ∈ R [t1 6= t2 ⇒ ∃ A ∈ QI:
tribute zu Attributkombinationen zusammenfassen, die an- t1 (A) 6= t2 (A)]
gefragt werden können.
Wie beim Datenbankentwurf reicht es auch für die Anga-
Für einen unerfahrenen Nutzer ist das Festlegen von sinn-
be von Quasi-Identifikatoren aus, wenn die minimale Men-
vollen Einstellungen nur schwer möglich. Die Frage, die sich
ge von Attributen angegeben wird, welche die Eigenschaft
ihm stellt, ist nicht die, ob er seine persönlichen Daten schüt-
eines QI hat. Eine solche Menge wird als minimaler Quasi-
zen soll, sondern vielmehr, welche Daten es wert sind, ge-
Identifikator bezeichnet.
schützt zu werden. Zur Kennzeichnung schützenswerter Da-
ten werden u.a. sogenannte Quasi-Identifikatoren [2] verwen- minimaler Quasi-Identifikator. X ist ein minimaler
det. In diesem Artikel stellen wir einen neuen Ansatz vor, Quasi-Identifikator (mQI), wenn X ein Quasi-Identifikator
mit dem Quasi-Identifikatoren schnell und vollständig er- ist und jede nicht-leere Teilmenge Y von X kein Quasi-
kannt werden können. Identifikator ist.
Der Rest des Artikels ist wie folgt strukturiert: Kapitel 2 X ist mQI: X ist QI ∧ (@ Y ⊂ X: (Y 6= ) ∧ (Y ist QI))
gibt einen aktuellen Überblick über den Stand der Forschung
Insbesondere ist X kein minimaler Quasi-Identifikator,
im Bereich der Erkennung von Quasi-Identifikatoren. Im fol-
wenn eine Teilmenge X-{A} von X mit A ∈ X existiert,
genden Kapitel gehen wir detailliert darauf ein, wie schüt-
die ein Quasi-Identifikator ist. Das Finden von allen Quasi-
zenswerte Daten definiert sind und wie diese effizient erkannt
Identifikatoren stellt ein NP-vollständiges Problem dar, weil
werden können. Kapitel 4 evaluiert den Ansatz anhand eines
die Menge der zu untersuchenden Teilmengen exponentiell
Datensatzes. Das letzte Kapitel fasst den Beitrag zusammen
zur Anzahl der Attribute einer Relation steigt. Besteht eine
und gibt einen Ausblick auf zukünftige Arbeiten.
Relation aus n Attributen, so existieren insgesamt 2n Attri-
butkombinationen, für die ermittelt werden muss, ob sie ein
2. STAND DER TECHNIK QI sind.
In diesem Kapitel stellen wir bestehende Konzepte zur In [12] stellen Motwani und Xu einen Algorithmus zum ef-
Ermittlung von Quasi-Identifikatoren (QI) vor. Außerdem fizienten Erkennen von minimalen Quasi-Identifikatoren vor.
werden Techniken vorgestellt, die in unseren Algorithmus Dieser baut auf die von Mannila et. al [10] vorgeschlagene,
eingefloßen sind. ebenenweise Erzeugung von Attributmengen auf. Dabei wird
die Minimalitätseigenschaft von Quasi-Identifikatoren sofort
2.1 Quasi-Identifikatoren erkannt und der Suchraum beim Durchlauf auf der nächsten
Zum Schutz personenbezogener Daten existieren Konzep- Ebene eingeschränkt.
te wie k-anonymity [16], l-diversity [8] und t-closeness [7]. Der Algorithmus ist effizienter als alle 2n Teilmengen zu
Diese Konzepte unterteilen die Attribute einer Relation in testen, allerdings stellt die von Big-Data-Anwendungen er-
Schlüssel, Quasi-Identifikatoren, sensitive Daten und sons- zeugte Datenmenge eine neue Herausforderung dar. Insbe-
tige Daten. Ziel ist es, dass die sensitiven Daten sich nicht sondere die hohe Dimensionalität und die Vielfalt der Daten
eindeutig zu einer bestimmten Person zuordnen lassen. Da sind ernst zu nehmende Probleme. Aus diesem Grund schla-
durch Schlüsselattribute Tupel eindeutig bestimmt werden gen wir im folgenden Kapitel einen neuen Algorithmus vor,
können, dürfen diese unter keinen Umständen zusammen der auf den Algorithmus von Motwani und Xu aufsetzt.
mit den sensitiven Attributen veröffentlicht werden.
Während Schlüssel im Laufe des Datenbankentwurfes fest- 2.2 Sideways Information Passing
gelegt werden, lassen sich Quasi-Identifikatoren erst beim Der von uns entwickelte Algorithmus verwendet Techni-
Vorliegen der Daten feststellen, da sie von den konkreten ken, die bereits beim Sideways Information Passing (SIP,
Attributwerten der Relation abhängen. Der Begriff Quasi- [4]) eingesetzt werden. Der grundlegende Ansatz von SIP
Identifikator wurde von Dalenius [2] geprägt und bezeichnet besteht darin, dass während der Ausführung von Anfrage-
a subset of attributes that can uniquely identify most tuples plänen Tupel nicht weiter betrachtet werden, sofern mit Si-
”
in a table“. cherheit feststeht, dass sie keinen Bezug zu Tupeln aus an-
Für most tuples“ wird häufig ein Grenzwert p festge- deren Relationen besitzen.
”
legt, der bestimmt, ob eine Attributkombination ein Quasi- Durch das frühzeitige Erkennen solcher Tupel wird der
Identifikator ist oder nicht. Dieser Grenzwert lässt sich bei- zu betrachtende Suchraum eingeschränkt und die Ausfüh-
spielsweise in relationalen Datenbanken durch zwei SQL- rungszeit von Anfragen reduziert. Besonders effektiv ist die-
Anfragen wie folgt bestimmen: ses Vorgehen, wenn das Wissen über diese magic sets“ [14]
”
zwischen den Teilen eines Anfrageplans ausgetauscht und
p = COUNT DISTINCT *COUNT
FROM (SELECT FROM table)
∗ FROM table
in höheren Ebenen des Anfrageplans mit eingebunden wird.
(1) Beim SIP werden zudem weitere Techniken wie Bloomjoins
Wird für p der Wert 1 gewählt, so sind die gefundenen QI [9] und Semi-Joins eingesetzt um den Anfrageplan weiter zu
mit diesem Grenzwert auch Schlüssel der Relation. Um eine optimieren.
Vergleichbarkeit unseres Algorithmus mit dem von Motwani
und Xu zu gewährleisten, verwenden wir ebenfalls die in (1) 2.3 Effiziente Erfragung von identifizieren-
definierte distinct ratio“ (nach [12]). den Attributmengen
”
Da es für den Ausdruck die meisten“ keinen standardisier-
” ≥p In [5] wird ein Algorithmus zur Ermittlung von identi-
ten Quantor gibt, formulieren wir ihn mit dem Zeichen: ∀ , fizierenden Attributmengen (IA) in einer relationalen Da-
wobei p den Prozentsatz der eindeutig identifizierbaren Tu- tenbank beschrieben. Wird für eine Attributmenge erkannt,
dass diese eine IA für eine Relation R ist, so sind auch alle Algorithm 1: bottomUp
Obermengen dieser Attributmenge IA für R. Ist für eine Re- Data: database table tbl, list of attributes elements
lation bestehend aus den Attributen A, B und C bekannt, Result: a set with all minimal QI qiLowerSet
dass B eine identifizierende Attributmenge ist, dann sind initialization();
auch AB, BC und ABC eine IA der Relation. for element in elements do
Ist eine Attributmenge hingegen keine IA für R, so sind set := set ∪ {element}
auch alle Teilmengen dieser Attributmenge keine IA. Wenn end
beispielsweise AC keine IA für R ist, dann sind auch weder A while set is not empty do
noch C identifizierende Attributmengen für R. Attributmen- for Set testSet: set do
gen, die keine identifizierende Attributmenge sind, werden double p := getPercentage(testSet, tbl);
als negierte Schlüssel bezeichnet. if p ≥ threshold then
Der in [5] vorgestellte Algorithmus nutzt diese Eigenschaf- qiLowerSet := qiLowerSet ∪ {testSet};
ten um anhand eines Dialoges mit dem Nutzer die Schlüs- end
seleigenschaften einer bereits existierenden Relation festzu-
end
legen. Dabei wird dem Nutzer ein Ausschnitt der Relations-
set := buildNewLowerSet(set, elements);
tabelle präsentiert anhand derer entschieden werden soll, ob
end
eine Attributkombination Schlüssel ist oder nicht. Wird in
return qiLowerSet;
einer Teilrelation festgestellt, dass die Attributmenge Tu-
pel mit gleichen Attributwerten besitzt, so kann die Attri-
butkombination für die Teilmenge, als auch für die gesamte
Relation kein Schlüssel sein. Algorithm 2: buildNewLowerSet
Data: current lower set lSet, list of attributes
elements
3. ALGORITHMUS Result: the new lower set lSetNew
In diesem Kapitel stellen wir einen neuen Algorithmus Set lSetNew := new Set();
zum Finden von minimalen Quasi-Identifikatoren vor. Der for Set set: lSet do
Algorithmus beschränkt sich dabei auf die Einschränkung for Attribut A: elements do
der zu untersuchenden Attributkombinationen. Der entwi- if @q ∈ qiLowerSet : q ⊆ set then
ckelte Ansatz führt dabei den von [12] vorgestellten Bottom- lSetNew := lSetNew ∪ {set ∪ {A}};
Up-Ansatz mit einen gegenläufigen Top-Down-Verfahren zu- end
sammen. end
3.1 Bottom-Up end
return lSetNew;
Der von Motwani und Xu in [12] vorgestellte Ansatz zum
Erkennen aller Quasi-Identifikatoren innerhalb einer Rela-
tion nutzt einen in [10] präsentierten Algorithmus. Dabei
wird für eine Relation mit n Attributen ebenenweise von gesetzte QIs besitzt, da so der Suchraum gleich zu Beginn
den einelementigen zu n-elementigen Attributkombinatio- stark eingeschränkt wird.
nen Tests durchgeführt. Wird für eine i-elementige (1≤i testSet: set do
double p := getPercentage(testSet, tbl); Passing [4] untereinander ausgetauscht. Es wird pro Berech-
if p < threshold then nungsschritt entweder die Top-Down- oder die Bottom-Up-
optOutSet := optOutSet ∪ {subset}; Methode angewandt und das Ergebnis an die jeweils ande-
else re Methode übergeben. Der Algorithmus terminiert, sobald
qiUpperSet := qiUpperSet ∪ {testSet}; alle Attributebenen durch einen der beiden Methoden abge-
for Set o: qiSet do arbeitet wurden oder das Bottom-Up-Vorgehen keine Attri-
if testSet ⊂ o then butkombinationen mehr zu überprüfen hat. In Abbildung 1
qiUpperSet := qiUpperSet - {o}; ist die Arbeitsweise des Algorithmus anhand einer Beispiel-
end relation mit sechs Attributen dargestellt. Die rot markierten
end Kombinationen stehen dabei für negierte QI, grün markierte
end für minimale QI und gelb markierte für potentiell minimale
end QI.
set := buildNewUpper(set); Um zu entscheiden, welcher Algorithmus im nächsten Zy-
end klus angewandt wird, wird eine Wichtungsfunktion einge-
return qiUpperSet; führt. Die Überprüfung einer einzelnen Attributkombinati-
on auf Duplikate hat eine Laufzeit von O(n*log(n)), wobei
n die Anzahl der Tupel in der Relation ist. Die Überprü-
Der Top-Down-Ansatz hebt die Nachteile des Bottom-Up- fung der Tupel hängt aber auch von der Größe der Attri-
Vorgehens auf: der Algorithmus arbeitet effizient, wenn QIs butkombination ab. Besteht ein zu überprüfendes Tupel aus
aus vielen Attributen zusammengesetzt sind und für den mehreren Attributen, so müssen im Datenbanksystem auch
Fall, dass die gesamte Relation kein QI ist, wird dies bei der mehr Daten in den Arbeitsspeicher für die Duplikaterken-
ersten Überprüfung erkannt und der Algorithmus terminiert nung geladen werden. Durch große Datenmengen werden
dann umgehend. Seiten schnell aus dem Arbeitsspeicher verdrängt, obwohl
Besteht die Relation hingegen aus vielen kleinen QIs, dann sie später wieder benötigt werden. Dadurch steigt die Re-
wird der Suchraum erst zum Ende des Algorithmus stark chenzeit weiter an.
eingeschränkt. Ein weiterer Nachteil liegt in der erhöhten Für eine vereinfachte Wichtungsfunktion nehmen wir an,
Rechenzeit, auf die in der Evaluation näher eingegangen dass alle Attribute den gleichen Speicherplatz belegen. Die
wird. Anzahl der Attribute in einer Attributkombination bezeich-
nen wir mit m. Für die Duplikaterkennung ergibt sich dann
3.3 Bottom-Up+Top-Down eine Laufzeit von O((n*m)*log(n*m)).
Der in diesem Artikel vorgeschlagene Algorithmus kom- Da die Anzahl der Tupel für jede Duplikaterkennung kon-
biniert die oben vorgestellten Verfahren. Dabei werden die stant bleibt, kann n aus der Kostenabschätzung entfernt
Verfahren im Wechsel angewandt und das Wissen über (ne- werden. Die Kosten für die Überprüfung einer einzelnen
gierte) Quasi-Identifikatoren wie beim Sideways Information
Algorithm 5: bottomUpTopDown Die Evaluation erfolgte in einer Client-Server-Umgebung.
Data: database table tbl, list of attributes attrList Als Server dient eine virtuelle Maschine, die mit einer 64-Bit-
Result: a set with all minimal quasi-identifier qiSet CPU (vier Kerne @ 2 GHz und jeweils 4 MB Cache) und 4
attrList.removeConstantAttributes(); GB Arbeitsspeicher ausgestattet ist. Auf dieser wurde eine
Set upperSet := new Set({attrList}); MySQL-Datenbank mit InnoDB als Speichersystem verwen-
Set lowerSet := new Set(attrList); det. Der Client wurde mit einem i7-3630QM als CPU betrie-
// Sets to check for each algorithm ben. Dieser bestand ebenfalls aus vier Kernen, die jeweils
int bottom := 0; über 2,3 GHz und 6 MB Cache verfügten. Als Arbeitsspei-
int top := attrList.size(); cher standen 8 GB zur Verfügung. Als Laufzeitumgebung
while (bottom<=top) or (lowerSet is empty) do wurde Java SE 8u5 eingesetzt.
calculateWeights(); Der Datensatz wurde mit jedem Algorithmus getestet.
if isLowerSetNext then Um zu ermitteln, wie die Algorithmen sich bei verschiede-
bottomUp(); nen Grenzwerten für Quasi-Identifikatoren verhalten, wur-
buildNewLowerSet(); den die Tests mit 10 Grenzwerten zwischen 50% und 99%
bottom++; wiederholt.
// Remove new QI from upper set Die Tests mit den Top-Down- und Bottom-Up-
modifyUpperSet(); Algorithmen benötigten im Schnitt gleich viele Tablescans
(siehe Abbildung 2). Die Top-Down-Methode lieferte bes-
else
sere Ergebnisse bei hohen QI-Grenzwerten, Bottom-Up
topDown();
ist besser bei niedrigeren Grenzwerten. Bei der Laufzeit
buildNewUpperSet();
(siehe Abbildung 3) liegt die Bottom-Up-Methode deutlich
top--;
vor dem Top-Down-Ansatz. Grund hierfür sind die großen
// Remove new negated QI from lower set
Attributkombinationen, die der Top-Down-Algorithmus zu
modifyLowerSet();
Beginn überprüfen muss.
end Der Bottom-Up+Top-Down-Ansatz liegt hinsichtlich
end Laufzeit als auch bei der Anzahl der Attributvergleiche
qiSet := qiLowerSet ∪ qiUpperSet; deutlich vorne. Die Anzahl der Tablescans konnte im Ver-
return qiSet; gleich zum Bottom-Up-Verfahren zwischen 67,4% (4076
statt 12501 Scans; Grenzwert: 0.5) und 96,8% (543 statt
16818 Scans; Grenzwert 0.9) reduziert werden. Gleiches gilt
Attributkombination mit m Attributen beträgt demnach für die Laufzeit (58,1% bis 97,5%; siehe Abbildung 3).
O((m*log(m)).
Die Gesamtkosten für das Überprüfen der möglichen
Quasi-Identifikatoren werden mit WAV G bezeichnet. WAV G 6000
Anzahl Tablescans

ergibt sich aus dem Produkt für das Überprüfen einer ein-
zelnen Attributkombination und der Anzahl der Attribut-
kombinationen (AttrKn ) mit n Attributen. 4000

WAV G := AttrKn ∗ log(m) ∗ m (2) 2000
Soll die Wichtungsfunktion präziser sein, so lässt sich der
Aufwand abschätzen, indem für jede Attributkombination
X die Summe s über die Attributgrößen von X gebildet und 0
anschließend gewichtet wird. Die Einzelgewichte werden an- 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
schließend zum Gesamtgewicht aufsummiert.
Anzahl Attribute in der Attributkombination

Brute-Force
P P
WAV G := log(s) ∗ s; s = size(A) (3)
X∈AttrKn A∈X Bottom-Up
Diese Wichtung eignet sich allerdings nur, wenn Zugang Top-Down
zu den Metadaten der Datenbankrelation besteht. Bottom-Up+Top-Down (AVG)

4. EVALUATION Abbildung 2: Verhältnis von der Anzahl der Attri-
Für die Evaluation des Algorithmus wurde die Adult“- bute in den Attributkombinationen zur Anzahl von
” Tablescans (Adult-DB, Grenzwert 90%)
Relation aus dem UCI Machine Learning Repository [6] ver-
wendet. Die Relation besteht aus anonymisierten, personen-
bezogenen Daten, bei denen Schlüssel sowie Vor- und Nach- Wie in Abbildung 3 zu erkennen ist, nimmt die Lauf-
name von Personen entfernt wurden. Die übrigen 15 Attri- zeit beim Bottom-Up+Top-Down-Verfahren im Grenz-
bute enthalten Angaben zu Alter, Ehestand, Staatsangehö- wertbereich von 70%-90% stark ab. Interessant ist dies
rigkeit und Schulabschluss. Die Relation besteht insgesamt aus zwei Gründen. Erstens nimmt die Anzahl der Quasi-
aus 32561 Tupeln, die zunächst im CSV-Format vorlagen Identifikatoren bis 90% ebenfalls ab (179 bei 50%, 56 bei
und in eine Datenbank geparst wurden. 90%). Dies legt nahe, dass die Skalierung des Verfahrens
neben der Dimension der Relation (Anzahl von Tupel und
Attributen) auch von der Anzahl der vorhandenen QIs Bekanntmachung vom 14. Januar 2003, das zuletzt
abhängt. Um den Zusammenhang zu bestätigen, sind aber durch Artikel 1 des Gesetzes vom 14. August 2009
weitere Untersuchungen erforderlich. geändert worden ist, 2010.
Zweitens wird dieser Grenzwertbereich in der Literatur [2] T. Dalenius. Finding a Needle In a Haystack or
[13] häufig benutzt, um besonders schützenswerte Daten her- Identifying Anonymous Census Records. Journal of
vorzuheben. Durch die gute Skalierung des Algorithmus in Official Statistics, 2(3):329–336, 1986.
diesem Bereich lassen sich diese QIs schnell feststellen. [3] H. Grunert. Privacy Policy for Smart Environments.
http://www.ls-dbis.de/pp4se, 2014. zuletzt
aufgerufen am 17.07.2014.
8000 [4] Z. G. Ives and N. E. Taylor. Sideways information
Laufzeit in Sekunden

passing for push-style query processing. In Data
6000 Engineering, 2008. ICDE 2008. IEEE 24th
International Conference on, pages 774–783. IEEE,
4000 2008.
[5] M. Klettke. Akquisition von Integritätsbedingungen in
2000 Datenbanken. PhD thesis, Universität Rostock, 1997.
[6] R. Kohavi and B. Becker. Adult Data Set.
http://archive.ics.uci.edu/ml/datasets/Adult,
0 1996. zuletzt aufgerufen am 17.07.2014.
50 60 70 80 90 95 99 [7] N. Li, T. Li, and S. Venkatasubramanian. t-Closeness:
Grenzwert in % Privacy Beyond k-Anonymity and l-Diversity. In
ICDE, volume 7, pages 106–115, 2007.
Bottom-Up [8] A. Machanavajjhala, D. Kifer, J. Gehrke, and
Top-Down M. Venkitasubramaniam. l-diversity: Privacy beyond
Bottom-Up+Top-Down(AVG) k-anonymity. ACM Transactions on Knowledge
Discovery from Data (TKDD), 1(1):3, 2007.
[9] L. F. Mackert. R* optimizer validation and
Abbildung 3: Vergleich der Laufzeit der verschiede- performance evaluation for distributed queries. In
nen Algorithmen (Adult-DB) Readings in database systems, pages 219–229. Morgan
Kaufmann Publishers Inc., 1988.
[10] H. Mannila, H. Toivonen, and A. I. Verkamo.
5. AUSBLICK Discovery of frequent episodes in event sequences.
In dieser Arbeit stellten wir einen effizienten Algorithmus Data Mining and Knowledge Discovery, 1(3):259–289,
zur Erkennung von QI in hochdimensionalen Daten vor. An- 1997.
hand eines Beispiels mit Sensordaten zeigten wir die Eignung [11] D. Moos. Konzepte und Lösungen für
in Assistenzsystemen. Darüber hinaus ermitteln wir derzeit, Datenaufzeichnungen in heterogenen dynamischen
inwiefern sich QIs in temporalen Datenbanken feststellen Umgebungen. Bachelorarbeit, Universität Rostock,
lassen. Das so gewonnene Wissen über schützenswerte Daten 2011.
wird in unser Gesamtprojekt zur datenschutzfreundlichen [12] R. Motwani and Y. Xu. Efficient algorithms for
Anfrageverarbeitung in Assistenzsystemen eingebunden. masking and finding quasi-identifiers. In Proceedings
In späteren Untersuchungen werden wir testen, welche of the Conference on Very Large Data Bases (VLDB),
weiteren Quasi-Identifikatoren sich aus der Kombination pages 83–93, 2007.
von Daten verschiedener Relationen ableiten lassen. Der [13] P. Samarati and L. Sweeney. Protecting privacy when
dafür verwendete Datensatz besteht aus Sensordaten, die disclosing information: k-anonymity and its
im Smart Appliance Lab des Graduiertenkollegs MuSA- enforcement through generalization and suppression.
MA durch ein Tool [11] aufgezeichnet wurden. Die Daten Technical report, Technical report, SRI International,
umfassen dabei Bewegungsprofile, die mittels RFID-Tags 1998.
und einen Sensfloor [15] erfasst wurden, aber auch Infor- [14] P. Seshadri, J. M. Hellerstein, H. Pirahesh, T. Leung,
mationen zu Licht und Temperatur. Eine Verknüpfung der R. Ramakrishnan, D. Srivastava, P. J. Stuckey, and
Basis-Relationen erfolgt dabei über die ermittelten Quasi- S. Sudarshan. Cost-based optimization for magic:
Identifikatoren. Algebra and implementation. In ACM SIGMOD
Record, volume 25, pages 435–446. ACM, 1996.
6. DANKSAGUNG [15] A. Steinhage and C. Lauterbach. Sensfloor (r): Ein
Hannes Grunert wird durch die Deutsche Forschungsge- AAL Sensorsystem für Sicherheit, Homecare und
meinschaft (DFG) im Rahmen des Graduiertenkollegs 1424 Komfort. Ambient Assisted Living-AAL, 2008.
(Multimodal Smart Appliance Ensembles for Mobile Appli- [16] L. Sweeney. k-anonymity: A model for protecting
cations - MuSAMA) gefördert. Wir danken den anonymen privacy. International Journal of Uncertainty,
Gutachtern für ihre Anregungen und Kommentare. Fuzziness and Knowledge-Based Systems,
10(05):557–570, 2002.
7. LITERATUR [17] M. Weiser. The computer for the 21st century.
[1] Bundesrepublik Deutschland. Scientific american, 265(3):94–104, 1991.
Bundesdatenschutzgesetz in der Fassung der